oj.uz

답안 #49194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49194 2018-05-23T14:26:21 Z tmwilliamlin168 호화 벙커 (IZhO13_burrow) C++14
100 / 100
 560 ms 4732 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');
	putchar_unlocked('\n');
}

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:57: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 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 3 ms 608 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Correct 6 ms 1160 KB Output is correct
9 Correct 9 ms 1344 KB Output is correct
10 Correct 24 ms 1392 KB Output is correct
11 Correct 41 ms 1620 KB Output is correct
12 Correct 24 ms 2644 KB Output is correct
13 Correct 31 ms 2644 KB Output is correct
14 Correct 68 ms 2644 KB Output is correct
15 Correct 76 ms 2644 KB Output is correct
16 Correct 82 ms 2644 KB Output is correct
17 Correct 89 ms 2680 KB Output is correct
18 Correct 260 ms 3068 KB Output is correct
19 Correct 234 ms 3452 KB Output is correct
20 Correct 504 ms 3828 KB Output is correct
21 Correct 417 ms 4220 KB Output is correct
22 Correct 533 ms 4648 KB Output is correct
23 Correct 560 ms 4732 KB Output is correct
24 Correct 407 ms 4732 KB Output is correct
25 Correct 344 ms 4732 KB Output is correct