oj.uz

Submission #1108535

# Submission time Handle Problem Language Result Execution time Memory
1108535 2024-11-04T11:20:28 Z brover29 Luxury burrow (IZhO13_burrow) C++17
0 / 100
 2000 ms 5456 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2480 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 7 ms 2640 KB Output is correct
6 Correct 18 ms 2640 KB Output is correct
7 Correct 9 ms 2384 KB Output is correct
8 Correct 617 ms 4944 KB Output is correct
9 Execution timed out 2067 ms 5456 KB Time limit exceeded
10 Halted 0 ms 0 KB -