oj.uz

답안 #49196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49196 2018-05-23T14:28:37 Z tmwilliamlin168 호화 벙커 (IZhO13_burrow) C++14
100 / 100
 415 ms 4588 KB 
#include <bits/stdc++.h>
using namespace std;

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, count = 0;
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
}

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() {
	n=in(), m=in(), k=in();
	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			a[i][j]=in();
	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;
	}
	out(rb);
	putchar_unlocked(' ');
	out(a2);
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:53: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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 5 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 4 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 5 ms 904 KB Output is correct
9 Correct 9 ms 1296 KB Output is correct
10 Correct 23 ms 1468 KB Output is correct
11 Correct 39 ms 1484 KB Output is correct
12 Correct 21 ms 2508 KB Output is correct
13 Correct 29 ms 2508 KB Output is correct
14 Correct 61 ms 2508 KB Output is correct
15 Correct 62 ms 2508 KB Output is correct
16 Correct 68 ms 2508 KB Output is correct
17 Correct 58 ms 2516 KB Output is correct
18 Correct 174 ms 2900 KB Output is correct
19 Correct 193 ms 3412 KB Output is correct
20 Correct 415 ms 3948 KB Output is correct
21 Correct 322 ms 4076 KB Output is correct
22 Correct 398 ms 4588 KB Output is correct
23 Correct 407 ms 4588 KB Output is correct
24 Correct 308 ms 4588 KB Output is correct
25 Correct 277 ms 4588 KB Output is correct