Submission #1165079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165079		12345678	Strah (COCI18_strah)	C++20	110 / 110	139 ms	35844 KiB

strah

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e3+5;

ll n, m, h[nx][nx], l[nx], r[nx], rt, res;
char mp[nx][nx];

ll func(ll x)
{
    return (x*x*(x+1)/2)-(((x*(x+1)*(2*x+1))/6)-((x*(x+1))/2));
}

void dfs(int u, int lb, int rb, int p, int row)
{
    if (l[u]!=-1) dfs(l[u], lb, u-1, h[row][u], row);
    if (r[u]!=-1) dfs(r[u], u+1, rb, h[row][u], row);
    ll cur=h[row][u]-p, lst=p-row, wid=rb-lb+1, vl=func(wid);
    //cout<<"debug "<<cur<<' '<<lst<<' '<<wid<<' '<<row<<'\n';
    res+=cur*lst*vl+vl*((cur*(cur+1))/2);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>mp[i][j];
    for (int i=1; i<=m; i++) h[n+1][i]=n+1;
    for (int i=n; i>=1; i--)
    {
        for (int j=1; j<=m; j++)
        {
            if (mp[i][j]=='#') h[i][j]=i;
            else h[i][j]=h[i+1][j];
        }
    }
    for (int i=1; i<=n; i++)
    {
        rt=-1;
        stack<ll> s;
        for (int j=1; j<=m; j++)
        {
            l[j]=r[j]=-1;
            while (!s.empty()&&h[i][s.top()]>h[i][j]) l[j]=s.top(), s.pop();
            if (s.empty()) rt=j;
            else r[s.top()]=j;
            s.push(j);
        }
        dfs(rt, 1, m, i, i);
    }
    cout<<res;
    //cout<<func(1)<<' '<<func(2)<<' '<<func(3)<<' '<<func(4)<<'\n';
}

/*
3 3
. . . 
. . . 
. . . 

2 3
.#.
..#
*/

• 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