oj.uz

Submission #85225

# Submission time Handle Problem Language Result Execution time Memory
85225 2018-11-19T00:03:57 Z FutymyClone Strah (COCI18_strah) C++14
110 / 110
 262 ms 37396 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int n, m, h[N][N], l[N], r[N], ans[N][N];
char a[N][N];
long long res = 0;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= m; i++) h[1][i] = (a[1][i] == '#' ? 0 : 1);
    for (int i = 2; i <= n; i++) for (int j = 1; j <= m; j++) h[i][j] = (a[i][j] == '#' ? 0 : h[i - 1][j] + 1);
    for (int i = 1; i <= n; i++) {
        deque <int> dq;
        for (int j = 1; j <= m; j++) {
            while (!dq.empty() && h[i][dq.front()] > h[i][j]) dq.pop_front();
            if (dq.empty()) l[j] = 0;
            else l[j] = dq.front();

            dq.push_front(j);
        }

        while (!dq.empty()) dq.pop_back();
        for (int j = m; j >= 1; j--) {
            while (!dq.empty() && h[i][dq.front()] >= h[i][j]) dq.pop_front();
            if (dq.empty()) r[j] = m + 1;
            else r[j] = dq.front();

            dq.push_front(j);
        }

        for (int j = 1; j <= m; j++) {
            ans[h[i][j]][r[j] - l[j]]--;
            ans[h[i][j]][r[j] - j]++;
            ans[h[i][j]][j - l[j]]++;
            ans[h[i][j]][0]--;
            //cout << l[j] << " " << r[j] << "\n";
        }
    }

    for (int i = 1; i <= n + 1; i++) for (int j = 1; j <= m + 1; j++) ans[i][j] += ans[i][j - 1];
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) ans[i][j] += ans[i + 1][j] + ans[i][j + 1] - ans[i + 1][j + 1];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) res += 1LL * ans[i][j] * i * j;
    cout << res;
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 612 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 2 ms 612 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4312 KB Output is correct
2 Correct 10 ms 4404 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4496 KB Output is correct
2 Correct 10 ms 4588 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4808 KB Output is correct
2 Correct 10 ms 4916 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16516 KB Output is correct
2 Correct 153 ms 28524 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 28524 KB Output is correct
2 Correct 233 ms 35936 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 35936 KB Output is correct
2 Correct 180 ms 35936 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 35936 KB Output is correct
2 Correct 188 ms 35936 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 37204 KB Output is correct
2 Correct 262 ms 37396 KB Output is correct