Submission #1108535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108535		brover29	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2067 ms	5456 KiB

burrow

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

ll n,m,k,a[1005][1005],pref[1005][1005];
ll calc(ll xa,ll ya,ll xb,ll yb){
    return pref[xb][yb]-pref[xa-1][yb]-pref[xb][ya-1]+pref[xa-1][ya-1];
}
ll check(ll x){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(a[i][j]>=x);
        }
    }ll ans=0;
    for(ll xa=1;xa<=n;xa++){
        for(ll ya=1;ya<=m;ya++){
            for(ll xb=xa;xb<=n;xb++){
                for(ll yb=ya;yb<=m;yb++){
                    if(calc(xa,ya,xb,yb)==(xb-xa+1)*(yb-ya+1)&&(xb-xa+1)*(yb-ya+1)>=k){
                        ans=max(ans,(xb-xa+1)*(yb-ya+1));
                    }
                }
            }
        }
    }
    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(check(mid))l=mid;
        else r=mid-1;
        //cout<<l<<' '<<r<<' '<<bool(check(mid))<<'\n';
    }
    cout<<l<<' '<<check(l);
}

• Subtask 1: 0 / 100