Guest User

E

a guest
Aug 26th, 2016
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const ll INF = (ll) 1e18;
  8.  
  9. const int N = 2222;
  10.  
  11. int R[N][N];
  12. int L[N][N];
  13. int U[N][N];
  14. int D[N][N];
  15. string s[N];
  16.  
  17. struct Bit {
  18.     vector<int> f;
  19.  
  20.     Bit(int n) { f.assign(n, 0); }
  21.  
  22.     void upd(int i, int by) {
  23.         for (; i < f.size(); i = (i | (i + 1)))
  24.             f[i] += by;
  25.     }
  26.  
  27.     int get(int i) {
  28.         int res = 0;
  29.         for (; i >= 0; i = (i & (i + 1)) - 1)
  30.             res += f[i];
  31.         return res;
  32.     }
  33.  
  34.     int get(int l, int r) {
  35.         return get(r) - get(l - 1);
  36.     }
  37. };
  38.  
  39. vector<int> at[N];
  40.  
  41.  
  42. int main() {
  43.     ios_base::sync_with_stdio(0);
  44.     int n;
  45.     cin >> n;
  46.     for (int i = 0; i < n; i++) {
  47.         cin >> s[i];
  48.     }
  49.     for (int i = 0; i < n; i++) {
  50.         int last = -1;
  51.         for (int j = 0; j < n; j++) {
  52.             if (s[i][j] == '0')
  53.                 last = j;
  54.             L[i][j] = last;
  55.         }
  56.         last = n;
  57.         for (int j = n - 1; j >= 0; j--) {
  58.             if (s[i][j] == '0')
  59.                 last = j;
  60.             R[i][j] = last;
  61.         }
  62.     }
  63.     for (int j = 0; j < n; j++) {
  64.         int last = -1;
  65.         for (int i = 0; i < n; i++) {
  66.             if (s[i][j] == '0')
  67.                 last = i;
  68.             U[i][j] = last;
  69.         }
  70.         last = n;
  71.         for (int i = n - 1; i >= 0; i--) {
  72.             if (s[i][j] == '0')
  73.                 last = i;
  74.             D[i][j] = last;
  75.         }
  76.     }
  77.     ll res = 0;
  78.     for (int i = 0; i < n; i++)
  79.         for (int j = 0; j < n; j++) {
  80.             if (i != 0 && j != 0)
  81.                 continue;
  82.             for (int i = 0; i <= n; i++)
  83.                 at[i].clear();
  84.             Bit tree(n);
  85.             for (int d = 0; i + d < n && j + d < n; d++) {
  86.                 for (int v : at[d])
  87.                     tree.upd(v, -1);
  88.                 if (s[i + d][j + d] == '0')
  89.                     continue;
  90.                 int d_u = max(0, U[i + d][j + d] - i + 1);
  91.                 int d_l = max(0, L[i + d][j + d] - j + 1);
  92.                 int lo = max(d_u, d_l);
  93.                 assert(lo <= d);
  94.                 res += tree.get(lo, d);
  95.                 tree.upd(d, 1);
  96.                 int delD = min(D[i + d][j + d] - i, R[i + d][j + d] - j);
  97.                 at[delD].push_back(d);                  
  98.             }      
  99.         }
  100.     cout << res << endl;
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment