제출 #1126397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126397		brover29	호화 벙커 (IZhO13_burrow)	C++17	100 / 100	1291 ms	24092 KiB

burrow

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1005;
const string br="617283";

ll n,m,k,a[N][N],b[N][N],l[N],r[N],pref[N][N],c[N],st[N];

ll solvek(ll x){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            b[i][j]=(a[i][j]>=x);
            pref[i][j]=pref[i-1][j]+b[i][j];
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            ll l=i-1,r=n;
            while(l<r){
                ll mid=(r+l+1)>>1;
                if(pref[mid][j]-pref[i-1][j]==mid-i+1)l=mid;
                else r=mid-1;
            }
            c[j]=l-i+1;
        }
        ll sz=0;
        st[sz]=0;
        for(ll j=1;j<=m;j++){
            while(sz&&c[j]<=c[st[sz]]){
                sz--;
            }
            l[j]=st[sz];
            st[++sz]=j;
        }
        sz=0;
        st[sz]=m+1;
        for(ll j=m;j>=1;j--){
            while(sz&&c[j]<c[st[sz]]){
                sz--;
            }
            r[j]=st[sz];
            st[++sz]=j;
        }
        for(ll j=1;j<=m;j++){
            ans=max(ans,((r[j]-1)-(l[j]+1)+1)*c[j]);
           // cout<<l[j]<<' '<<r[j]<<'\n';
        }
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m>>k;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    ll l=1,r=1e9;
    while(l<r){
        ll mid=(r+l+1)>>1;
        if(solvek(mid)>=k)l=mid;
        else r=mid-1;
        //cout<<l<<' '<<r<<' '<<bool(check(mid))<<'\n';
    }
    cout<<r<<' '<<solvek(r);
}

• Subtask 1: 100 / 100