1 条题解
-
0陈烨鑫 (chenyexin) LV 10 @ 2024-3-28 21:25:05
#include<iostream> #include<cstdio> #include<cstring> #define int long long using namespace std; inline int read(){ int sum=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();} return sum*f; } int sum[505][505]; int t[2500070],tt[2500070]; int n,x,ans; signed main(){ n=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int x; x=read(); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=i;k++){ for(int l=1;l<=j;l++){ int tmp=sum[i][j]-sum[k-1][j]-sum[i][l-1]+sum[k-1][l-1]; t[tmp]++; } } for(int k=i+1;k<=n;k++){ for(int l=j+1;l<=n;l++){ int tmp=sum[k][l]-sum[i][l]-sum[k][j]+sum[i][j]; if(t[tmp]){ ans-=t[tmp]*tt[tmp]; tt[tmp]++; ans+=t[tmp]*tt[tmp]; } } } for(int k=1;k<=i;k++){ for(int l=1;l<=j;l++){ int tmp=sum[i][j]-sum[k-1][j]-sum[i][l-1]+sum[k-1][l-1]; t[tmp]--; } } for(int k=i+1;k<=n;k++){ for(int l=j+1;l<=n;l++){ int tmp=sum[k][l]-sum[i][l]-sum[k][j]+sum[i][j]; tt[tmp]--; } } for(int k=1;k<=i;k++){ for(int l=j+1;l<=n;l++){ int tmp=sum[i][l]-sum[i][j]-sum[k-1][l]+sum[k-1][j]; t[tmp]++; } } for(int k=i+1;k<=n;k++){ for(int l=1;l<=j;l++){ int tmp=sum[k][j]-sum[k][l-1]-sum[i][j]+sum[i][l-1]; if(t[tmp]){ ans-=t[tmp]*tt[tmp]; tt[tmp]++; ans+=t[tmp]*tt[tmp]; } } } for(int k=1;k<=i;k++){ for(int l=j+1;l<=n;l++){ int tmp=sum[i][l]-sum[i][j]-sum[k-1][l]+sum[k-1][j]; t[tmp]--; } } for(int k=i+1;k<=n;k++){ for(int l=1;l<=j;l++){ int tmp=sum[k][j]-sum[k][l-1]-sum[i][j]+sum[i][l-1]; tt[tmp]--; } } } } printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 2978
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 55
- 已通过
- 13
- 上传者