a53

match

a53
Mar 3rd, 2017
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. ///student George Popescu
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <vector>
  5. #define MOD 666013
  6. #define NMAX 175
  7. #define min(a,b) (a<b?a:b)
  8. using namespace std;
  9.  
  10. int a[NMAX][NMAX],b[NMAX][NMAX];
  11. long long pd[NMAX][NMAX],dp[NMAX][NMAX];
  12. int n1,n2,m1,m2,N1,N2;
  13. struct has
  14. {
  15. int x;
  16. long long s;
  17. };
  18. vector<has>v[MOD+1];
  19.  
  20. void fasuma()
  21. {
  22. int i,j;
  23. for(i=1;i<=n1;++i)
  24. for(j=1;j<=m1;++j)
  25. dp[i][j]=dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j];
  26.  
  27. for(i=1;i<=n2;++i)
  28. for(j=1;j<=m2;++j)
  29. pd[i][j]=pd[i-1][j] + pd[i][j-1] - pd[i-1][j-1] + b[i][j];
  30. }
  31. has pp(long long s,int x)
  32. {
  33. has X;
  34. X.s=s;X.x=x;
  35. return X;
  36. }
  37.  
  38. void bagahash(long long x)
  39. {
  40. int r=x%MOD;
  41. if(v[r].size() != 0)
  42. {
  43. for(int i=0;i<v[r].size();++i){
  44. if(v[r][i].s == x) {++v[r][i].x;return;}
  45. }
  46. v[r].push_back(pp(x,1));
  47. }
  48. else v[r].push_back(pp(x,1));
  49. }
  50.  
  51. int cauta(long long x)
  52. {
  53. int r=x%MOD;
  54. if(v[r].size() != 0)
  55. {
  56. for(int i=0; i<v[r].size();++i){
  57. if(v[r][i].s == x) {return v[r][i].x;}
  58. }
  59. return 0;
  60. }
  61. else return 0;
  62. }
  63.  
  64. int main()
  65. {
  66. int i,j,k;
  67. long long s;
  68. freopen("match.in","r",stdin);
  69. freopen("match.out","w",stdout);
  70. scanf("%d%d",&N1,&m1);
  71. n1=N1/m1;
  72. for(i=1;i<=n1;++i)
  73. for(j=1;j<=m1;++j)
  74. scanf("%d",&a[i][j]);
  75. scanf("%d%d",&N2,&m2);
  76. n2=N2/m2;
  77. for(i=1;i<=n2;++i)
  78. for(j=1;j<=m2;++j)
  79. scanf("%d",&b[i][j]);
  80. fasuma();
  81. //calculez sumele tuturor matricilor din a
  82. int l1=min(n1,m1);
  83. int l2=min(n2,m2);
  84. for(k=1;k<=l1;++k)
  85. for(i=1;i<=n1-k+1;++i)
  86. for(j=1;j<=m1-k+1;++j)
  87. {
  88. s=dp[i+k-1][j+k-1]+dp[i-1][j-1]-dp[i-1][j+k-1] - dp[i+k-1][j-1];
  89. bagahash(s);
  90. }
  91. int sol=0;
  92. for(k=1;k<=l2;++k)
  93. for(i=1;i<=n2-k+1;++i)
  94. for(j=1;j<=m2-k+1;++j)
  95. {
  96. s=pd[i+k-1][j+k-1]+pd[i-1][j-1]-pd[i-1][j+k-1] - pd[i+k-1][j-1];
  97. sol+=cauta(s);
  98. }
  99. printf("%d\n",sol);
  100. return 0;
  101. }
Add Comment
Please, Sign In to add comment