Submission #1318735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318735		vicvic	Strah (COCI18_strah)	C++20	110 / 110	87 ms	31884 KiB

strah

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX=2000;
int h[NMAX+5][NMAX+5], st[NMAX+5], l[NMAX+5], r[NMAX+5], y, n, m, ret;
void dfs (int nod, int st, int dr)
{
    if (st>dr)
        return;
    int le=nod-st, re=dr-nod;
    ret+=((re+1)*(le+2)*(le+1)/2+(le+1)*(re)*(re+1)/2)*(h[y][nod]*(h[y][nod]+1)/2);
    dfs (l[nod], st, nod-1);
    dfs (r[nod], nod+1, dr);
}
signed main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        s='#'+s;
        for (int j=1;j<=m;j++)
        {
            l[j]=r[j]=0;
            h[i][j]=h[i-1][j]+(s[j]=='.');
            if (s[j]=='#')
                h[i][j]=0;
        }
        int crt=0;
        for (int j=1;j<=m;j++)
        {
            int k=crt;
            while (k && h[i][st[k]]>h[i][j])
                k--;
            if (k+1<=crt)
                l[j]=st[k+1];
            if (k)
                r[st[k]]=j;
            st[crt=++k]=j;
        }
        y=i;
        dfs (st[1], 1, m);
    }
    cout << ret;
    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