Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "VILLA"
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- constexpr int N = 2e3 + 5;
- int m, n;
- string s[N];
- int a[N][N];
- int16_t last[N][N];
- int16_t start[N][N];
- ll x[N][N], y[N][N];
- void Read()
- {
- cin >> m >> n;
- for (int i = 1; i <= m; ++i)
- {
- cin >> s[i];
- s[i] = " " + s[i];
- for (int j = 1; j <= n; ++j)
- a[i][j] = (s[i][j] == '#') + a[i][j - 1];
- }
- }
- #define Get(x, y, z) (a[x][z] - a[x][y - 1])
- void Solve()
- {
- ll ans = m * n;
- for (int i = 1; i <= m; ++i)
- ans -= a[i][n];
- ans = ans * (ans + 1) / 2;
- for (int i = 1; i <= m; ++i)
- for (int j = 1; j <= n; ++j)
- {
- start[i][j] = -1;
- if (s[i][j] == '#')
- last[i][j] = j;
- else
- last[i][j] = last[i][j - 1];
- if (s[i][j] == '#')
- {
- start[i][j] = j;
- if (s[i][j - 1] == '#')
- start[i][j] = start[i][j - 1];
- }
- if (s[i][j] != '#')
- {
- int l = last[i][j],
- r = j;
- x[i][l] = x[i - 1][last[i - 1][l]] - l + a[i][l];
- y[i][r] = y[i - 1][s[i - 1][r] == '#' ? (start[i - 1][r] - 1) : r] + r - a[i][r];
- ans -= x[i][l] + y[i][r];
- /*for (int t = i; t && l < r; --t)
- {
- ans -= r - l - Get(t, l + 1, r);
- if (t != 1)
- {
- if (s[t - 1][r] == '#')
- r = start[t - 1][r] - 1;
- l = last[t - 1][l];
- }
- }*/
- }
- }
- cout << ans << endl;
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement