Submission #1108859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108859		brover29	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	1 ms	2384 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 l1,ll l2){
    for(ll i=1;i+l1-1<=n;i++){
        for(ll j=1;j+l2-1<=m;j++){
            if(calc(i,j,i+l1-1,j+l2-1)==l1*l2&&l1*l2>=k){
                return 1;
            }
        }
    }
    return 0;
}
ll solvex(ll l1){
    ll l=0,r=m;
    while(l<r){
        ll mid=(r+l+1)>>1;
        if(check(l1,mid))l=mid;
        else r=mid-1;
    }
    return l*l1;
}
ll solvek(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;
    ll l=1,r=n;
    for(ll i=1;i<=60;i++){
        ll m1=l+(r-l)/3;
        ll m2=r-(r-l)/3;
        if(solvex(m1)>solvex(m2))r=m2;
        else l=m1;
    }
    for(ll i=l;i<=r;i++){
       // cout<<i <<' '<<solvex(i)<<'\n';
        ans=max(ans,solvex(i));
    }
    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: 0 / 100