Submission #341116

#	Time	Username	Problem	Language	Result	Execution time	Memory
341116		juggernaut	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	488 ms	17900 KiB

burrow

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1005][1005],lb=1,rb=1e9,mb,a2,a3,b[1005][1005],l[1005],r[1005];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)cin>>a[i][j];
	while(lb<=rb) {
		mb=(lb+rb)>>1,a3=0;
		for(int i=n-1;i>=0;i--)
			for(int j=0; j<m;j++)
				b[i][j]=a[i][j]<mb?0:b[i+1][j]+1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				l[j]=j-1;
				while(l[j]>=0&&b[i][l[j]]>=b[i][j])l[j]=l[l[j]];
			}
			for(int j=m-1;j>=0;j--) {
				r[j]=j+1;
				while(r[j]<m&&b[i][r[j]]>=b[i][j])r[j]=r[r[j]];
				a3=max(b[i][j]*(r[j]-l[j]-1), a3);
			}
		}
		if(a3>=k) {
			lb=mb+1;
			a2=a3;
		} else
			rb=mb-1;
	}
	cout<<rb<<" "<<a2;
}

• Subtask 1: 100 / 100