Wannafly挑战赛5珂朵莉与宇宙

#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N=1E6+5; int n,f[N],sum,x; long long ans; int main() { cin>>n; f[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&x); sum+=x; for(int j=0;j*j<=i*10;j++) { if(sum>=j*j) ans+=f[sum-j*j]; } f[sum]++; } cout<<ans<<endl; } //求前缀和，然后标记比当前小完全平方数的数的个数，直接加在答案上。