제출 #1158654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158654		12345678	호화 벙커 (IZhO13_burrow)	C++20	100 / 100	456 ms	8364 KiB

burrow

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, m, k, vl[nx][nx], L=1, R=1e9, dp[nx][nx], mx, l[nx], r[nx], rt, h[nx], sz[nx];

void dfs(int u)
{
    sz[u]=1;
    if (l[u]!=-1) dfs(l[u]), sz[u]+=sz[l[u]];
    if (r[u]!=-1) dfs(r[u]), sz[u]+=sz[r[u]];
    mx=max(mx, sz[u]*h[u]);
}

bool solve(int x)
{
    //cout<<"here "<<x<<'\n';
    mx=0;
    for (int j=1; j<=m; j++) dp[0][j]=1;
    for (int i=1; i<=n; i++)
    {
        stack<int> s;
        rt=-1;
        for (int j=1; j<=m; j++)
        {
            if (vl[i][j]<x) dp[i][j]=i+1;
            else dp[i][j]=dp[i-1][j];
            h[j]=i-dp[i][j]+1;
            //if (x==1) cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<'\n';
            //cout<<"h "<<i<<' '<<j<<' '<<h[j]<<'\n';
            l[j]=r[j]=-1;
            while (!s.empty()&&h[s.top()]>=h[j]) l[j]=s.top(), s.pop();
            if (s.empty()) rt=j;
            else r[s.top()]=j;
            s.push(j);
        }
        dfs(rt);
        if (x==1) cout<<"here "<<x<<' '<<rt<<' '<<sz[rt]<<' '<<h[rt]<<'\n';
    }
    if (mx>=k) return 1;
    return 0;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<=n; i++) for (int j=1; j<=m ;j++) cin>>vl[i][j];
    while (L<R)
    {
        int md=(L+R+1)/2;
        if (solve(md)) L=md;
        else R=md-1;
    }
    solve(L);
    cout<<L<<' '<<mx;
}

• Subtask 1: 100 / 100