#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);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
