oj.uz

Submission #163914

# Submission time Handle Problem Language Result Execution time Memory
163914 2019-11-16T08:13:29 Z dolphingarlic Strah (COCI18_strah) C++14
110 / 110
 435 ms 67652 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll h[2020][2020], ans[2020][2020];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    FOR(i, 1, n + 1) {
        vector<pair<int, int>> v = {{0, 0}};
        FOR(j, 1, m + 1) {
            h[i][j] = h[i - 1][j] + 1;
            char c;
            cin >> c;
            if (c == '#') h[i][j] = 0;

            while (v.size() && v.back().second >= h[i][j]) v.pop_back();
            v.push_back({j, h[i][j]});

            for (int k = v.size() - 1; k; k--) {
                ans[v[k].second][j - v[k - 1].first]++;
                ans[v[k - 1].second][j - v[k - 1].first]--;
            }
        }
    }

    for (int i = n; i; i--) for (int j = m; j; j--) {
        ans[i][j] += ans[i + 1][j] + ans[i][j + 1] - ans[i + 1][j + 1];
    }

    ll tot = 0;
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) tot += i * j * ans[i][j];
    cout << tot;
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4372 KB Output is correct
2 Correct 11 ms 4216 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4196 KB Output is correct
2 Correct 11 ms 4344 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4216 KB Output is correct
2 Correct 11 ms 4216 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 24380 KB Output is correct
2 Correct 195 ms 50652 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 44872 KB Output is correct
2 Correct 281 ms 65084 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 28792 KB Output is correct
2 Correct 212 ms 53752 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 19416 KB Output is correct
2 Correct 354 ms 62712 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 67568 KB Output is correct
2 Correct 261 ms 67652 KB Output is correct