Submission #228190

#	Time	Username	Problem	Language	Result	Execution time	Memory
228190		VEGAnn	Strah (COCI18_strah)	C++14	110 / 110	215 ms	23928 KiB

strah

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 2010;
stack<pii> st;
char c[N][N];
int down[N][N], n, m;
ll ans = 0;

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

ll seg_arith(ll l, ll r){
    return arith(r) - arith(l - 1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> c[i][j];

    for (int j = 1; j <= m; j++){
        down[n + 1][j] = 0;

        for (int i = n; i > 0; i--)
            if (c[i][j] == '#')
                down[i][j] = 0;
            else down[i][j] = down[i + 1][j] + 1;
    }

    for (int i = 1; i <= n; i++){
        while (sz(st)) st.pop();

        ll sm = 0, real_sm = 0;

        for (int j = m; j > 0; j--){
            pii cr = MP(down[i][j], j);

            while (sz(st) && st.top() > cr){
                pii dl = st.top(); st.pop();
                int lf = dl.sd;
                int rt = m;

                if (sz(st))
                    rt = st.top().sd - 1;

                real_sm -= seg_arith(lf - j + 1, rt - j + 1) * arith(dl.ft);
                real_sm += seg_arith(lf - j + 1, rt - j + 1) * arith(cr.ft);
                sm -= (rt - lf + 1) * arith(dl.ft);
                sm += (rt - lf + 1) * arith(cr.ft);
            }

            st.push(cr);
            sm += arith(down[i][j]);
            real_sm += arith(down[i][j]);

            ans += real_sm;
            real_sm += sm;
        }
    }

    cout << ans;

    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