Submission #314842

#	Time	Username	Problem	Language	Result	Execution time	Memory
314842		Fischer	Strah (COCI18_strah)	C++14	110 / 110	301 ms	8312 KiB

strah

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2010;
char mat[maxn][maxn];
int n, m;
int arr[maxn], ta[maxn];
using ll = long long;
ll ans[maxn];

ll calc(ll x)  {
    return x * (x + 1) / 2;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> mat[i];
    }
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            arr[j + 1] = mat[i][j] != '#' ? arr[j + 1] + 1 : 0;
            ta[j + 1] = arr[j + 1];
        }
        stack<int> s;
        s.push(0); 
        ll sum = 0;
        for (int j = 1; j <= m; ++j) {
            ll delta = 0;
            int temp = j;
            while (!s.empty() && ta[s.top()] > ta[j]) {
                temp = s.top(); s.pop();
                delta += (calc(ta[temp]) - calc(ta[s.top()])) * calc(j - temp);
                sum -= (calc(ta[temp]) - calc(ta[s.top()])) * (j - temp);
            }
            delta -= (calc(ta[j]) - calc(ta[s.top()])) * calc(j - temp);
            sum += (calc(ta[j]) - calc(ta[s.top()])) * (j - temp);
            sum += calc(ta[j]);
            ans[j] = ans[j-1] + sum - delta;
            ta[temp] = ta[j];
            if (ta[j] > ta[s.top()]) {
                s.push(temp);
            }
        }
        for (int j = 1; j <= m; ++j) {
            res += ans[j];
        }
    }
    cout << res << endl;
    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