| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1330326 | snowavenode | 삶의 질 (IOI10_quality) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int R, C, H, W; cin >> R >> C >> H >> W;
vector<vector<int>> Q(R, vector<int>(C));
for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) cin >> Q[i][j];
int low = 1, high = R * C, ans = R * C;
while(low <= high) {
int mid = (low + high) / 2;
vector<vector<int>> pref(R+1, vector<int>(C+1, 0));
for(int i = 1; i <= R; i++) {
for(int j = 1; j <= C; j++) {
int val = (Q[i-1][j-1] <= mid ? -1 : 1);
pref[i][j] = val + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
}
}
bool ok = false;
for(int i = H; i <= R && !ok; i++) {
for(int j = W; j <= C; j++) {
int sum = pref[i][j] - pref[i-H][j] - pref[i][j-W] + pref[i-H][j-W];
if(sum < 0) {ok = true; break;}
}
}
if(ok) {ans = mid; high = mid - 1;}
else low = mid + 1;
}
cout << ans << endl;
return 0;
}