제출 #163914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163914		dolphingarlic	Strah (COCI18_strah)	C++14	110 / 110	435 ms	67652 KiB

strah

#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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11