Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll INF = (ll) 1e18;
- const int N = 2222;
- int R[N][N];
- int L[N][N];
- int U[N][N];
- int D[N][N];
- string s[N];
- struct Bit {
- vector<int> f;
- Bit(int n) { f.assign(n, 0); }
- void upd(int i, int by) {
- for (; i < f.size(); i = (i | (i + 1)))
- f[i] += by;
- }
- int get(int i) {
- int res = 0;
- for (; i >= 0; i = (i & (i + 1)) - 1)
- res += f[i];
- return res;
- }
- int get(int l, int r) {
- return get(r) - get(l - 1);
- }
- };
- vector<int> at[N];
- int main() {
- ios_base::sync_with_stdio(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> s[i];
- }
- for (int i = 0; i < n; i++) {
- int last = -1;
- for (int j = 0; j < n; j++) {
- if (s[i][j] == '0')
- last = j;
- L[i][j] = last;
- }
- last = n;
- for (int j = n - 1; j >= 0; j--) {
- if (s[i][j] == '0')
- last = j;
- R[i][j] = last;
- }
- }
- for (int j = 0; j < n; j++) {
- int last = -1;
- for (int i = 0; i < n; i++) {
- if (s[i][j] == '0')
- last = i;
- U[i][j] = last;
- }
- last = n;
- for (int i = n - 1; i >= 0; i--) {
- if (s[i][j] == '0')
- last = i;
- D[i][j] = last;
- }
- }
- ll res = 0;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++) {
- if (i != 0 && j != 0)
- continue;
- for (int i = 0; i <= n; i++)
- at[i].clear();
- Bit tree(n);
- for (int d = 0; i + d < n && j + d < n; d++) {
- for (int v : at[d])
- tree.upd(v, -1);
- if (s[i + d][j + d] == '0')
- continue;
- int d_u = max(0, U[i + d][j + d] - i + 1);
- int d_l = max(0, L[i + d][j + d] - j + 1);
- int lo = max(d_u, d_l);
- assert(lo <= d);
- res += tree.get(lo, d);
- tree.upd(d, 1);
- int delD = min(D[i + d][j + d] - i, R[i + d][j + d] - j);
- at[delD].push_back(d);
- }
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment