oj.uz

답안 #49195

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

#define getchar_unlocked getchar
#define putchar_unlocked putchar

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:56: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 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 6 ms 956 KB Output is correct
9 Correct 9 ms 1468 KB Output is correct
10 Correct 23 ms 1468 KB Output is correct
11 Correct 41 ms 1484 KB Output is correct
12 Correct 20 ms 2644 KB Output is correct
13 Correct 31 ms 2644 KB Output is correct
14 Correct 61 ms 2644 KB Output is correct
15 Correct 73 ms 2644 KB Output is correct
16 Correct 71 ms 2644 KB Output is correct
17 Correct 65 ms 2644 KB Output is correct
18 Correct 189 ms 3068 KB Output is correct
19 Correct 213 ms 3452 KB Output is correct
20 Correct 474 ms 3836 KB Output is correct
21 Correct 384 ms 4180 KB Output is correct
22 Correct 500 ms 4588 KB Output is correct
23 Correct 535 ms 4588 KB Output is correct
24 Correct 398 ms 4588 KB Output is correct
25 Correct 353 ms 4604 KB Output is correct