Submission #1302877

#TimeUsernameProblemLanguageResultExecution timeMemory
1302877PetrixLuxury burrow (IZhO13_burrow)C++20
100 / 100
285 ms16112 KiB
#include<iostream>
using namespace std;

int n,m,k;
int a[2001][2001];
int v[2001][2001];
int st[2001];
int dr[2001];


pair<int,int> solve(int x){
    int i,j,max1=0;
    for(i=n-1;i>=0;i--){
        for(j=0;j<m;j++){
            if(v[i][j]<x) a[i][j]=0;
            else a[i][j]=a[i+1][j]+1;
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            st[j]=j-1;
            while(st[j]>=0 && a[i][st[j]]>=a[i][j]) st[j]=st[st[j]];
        }
        for(j=m-1;j>=0;j--) {
            dr[j]=j+1;
            while(dr[j]<m && a[i][dr[j]]>=a[i][j]) dr[j]=dr[dr[j]];
            max1=max(max1,a[i][j]*(dr[j]-st[j]-1));
        }
    }
    if(max1>=k){
        return {1,max1};
    }else return {0,0};
}

int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int i,j,st1=1,dr1=1e9,mij,aux,rasp,rasp1;
	cin>>n>>m>>k;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)cin>>v[i][j];
    }
	while(st1<=dr1) {
		mij=(st1+dr1)/2;aux=0;
		auto it=solve(mij);
        if(it.first){
            st1=mij+1;rasp=mij;rasp1=it.second;
        }else dr1=mij-1;
	}
	cout<<rasp<<" "<<rasp1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...