oj.uz

Submission #341116

# Submission time Handle Problem Language Result Execution time Memory
341116 2020-12-29T03:06:10 Z juggernaut Luxury burrow (IZhO13_burrow) C++14
100 / 100
 488 ms 17900 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 5 ms 1132 KB Output is correct
9 Correct 8 ms 2028 KB Output is correct
10 Correct 22 ms 2284 KB Output is correct
11 Correct 46 ms 2924 KB Output is correct
12 Correct 24 ms 4460 KB Output is correct
13 Correct 30 ms 1644 KB Output is correct
14 Correct 75 ms 4076 KB Output is correct
15 Correct 76 ms 4076 KB Output is correct
16 Correct 80 ms 4588 KB Output is correct
17 Correct 82 ms 4844 KB Output is correct
18 Correct 232 ms 7908 KB Output is correct
19 Correct 222 ms 7788 KB Output is correct
20 Correct 456 ms 12268 KB Output is correct
21 Correct 380 ms 13676 KB Output is correct
22 Correct 476 ms 17900 KB Output is correct
23 Correct 488 ms 17772 KB Output is correct
24 Correct 353 ms 10732 KB Output is correct
25 Correct 334 ms 11116 KB Output is correct