Advertisement
Guest User

Untitled

a guest
Sep 29th, 2013
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. const int m = 2500000;
  7.  
  8. int n, a[51][51], sum[51][51], cnt[2 * m + 1];
  9. long long ans;
  10.  
  11. int getsum(int x, int y, int x2, int y2)
  12. {
  13.     return sum[x2][y2] - sum[x - 1][y2] - sum[x2][y - 1] + sum[x - 1][y - 1] + m;
  14. }
  15.  
  16. int main()
  17. {
  18.     //freopen("in", "r", stdin);
  19.    
  20.     scanf("%d", &n);
  21.  
  22.     for (int i = 1; i <= n; ++i)
  23.         for (int j = 1; j <= n; ++j)
  24.             scanf("%d", &a[i][j]);
  25.  
  26.     for (int i = 1; i <= n; ++i)
  27.         for (int j = 1; j <= n; ++j)
  28.             sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
  29.  
  30.     for (int i = 1; i <= n; ++i)
  31.         for (int j = 1; j <= n; ++j)
  32.         {
  33.             //down - right
  34.             for (int k = 1; k < i; ++k)
  35.                 for (int l = 1; l < j; ++l)
  36.                     cnt[getsum(k, l, i - 1, j - 1)]++;
  37.  
  38.             for (int k = i; k <= n; ++k)
  39.                 for (int l = j; l <= n; ++l)
  40.                     ans += cnt[getsum(i, j, k, l)];
  41.  
  42.             for (int k = 1; k < i; ++k)
  43.                 for (int l = 1; l < j; ++l)
  44.                     cnt[getsum(k, l, i - 1, j - 1)]--;
  45.  
  46.             //up - right                               
  47.             for (int k = n; k > i; --k)
  48.                 for (int l = 1; l < j; ++l)
  49.                     cnt[getsum(i + 1, l, k, j - 1)]++;
  50.  
  51.             for (int k = i; k > 0; --k)
  52.                 for (int l = j; l <= n; ++l)
  53.                     ans += cnt[getsum(k, j, i, l)];
  54.  
  55.             for (int k = n; k > i; --k)
  56.                 for (int l = 1; l < j; ++l)
  57.                     cnt[getsum(i + 1, l, k, j - 1)]--;
  58.         }
  59.  
  60.     cout << ans;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement