oj.uz

Submission #49192

# Submission time Handle Problem Language Result Execution time Memory
49192 2018-05-23T14:18:49 Z tmwilliamlin168 Luxury burrow (IZhO13_burrow) C++14
100 / 100
 540 ms 4732 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1000;
int n, m, k, a[mxN][mxN], lb=1, rb=1e9, mb, a2, a3, b[2][mxN], l[mxN], r[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.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)/2, a3=0;
		memset(b[n&1], 0, 4*m);
		for(int i=n-1; i>=0; --i) {
			for(int j=0; j<m; ++j)
				b[i&1][j]=a[i][j]<mb?0:b[i&1^1][j]+1;
			for(int j=0; j<m; ++j) {
				l[j]=j-1;
				while(l[j]>=0&&b[i&1][l[j]]>=b[i&1][j])
					l[j]=l[l[j]];
			}
			for(int j=m-1; j>=0; --j) {
				r[j]=j+1;
				while(r[j]<m&&b[i&1][r[j]]>=b[i&1][j])
					r[j]=r[r[j]];
				a3=max(b[i&1][j]*(r[j]-l[j]-1), a3);
			}
		}
		if(a3>=k) {
			lb=mb+1;
			a2=a3;
		} else
			rb=mb-1;
	}
	cout << rb << " " << a2;
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:20:31: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     b[i&1][j]=a[i][j]<mb?0:b[i&1^1][j]+1;
                              ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 17 ms 732 KB Output is correct
8 Correct 7 ms 1052 KB Output is correct
9 Correct 9 ms 1332 KB Output is correct
10 Correct 26 ms 1332 KB Output is correct
11 Correct 45 ms 1516 KB Output is correct
12 Correct 24 ms 2540 KB Output is correct
13 Correct 34 ms 2540 KB Output is correct
14 Correct 71 ms 2540 KB Output is correct
15 Correct 72 ms 2540 KB Output is correct
16 Correct 81 ms 2540 KB Output is correct
17 Correct 74 ms 2684 KB Output is correct
18 Correct 206 ms 3068 KB Output is correct
19 Correct 231 ms 3324 KB Output is correct
20 Correct 508 ms 3708 KB Output is correct
21 Correct 460 ms 4220 KB Output is correct
22 Correct 498 ms 4732 KB Output is correct
23 Correct 540 ms 4732 KB Output is correct
24 Correct 366 ms 4732 KB Output is correct
25 Correct 349 ms 4732 KB Output is correct