# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123444 | njoop | 삶의 질 (IOI10_quality) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
int r, c, h, w;
bool check(int val) {
vector<vector<int>> n(r+10, vector<int>(c+10, 0));
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(v[i][j] <= val) n[i+1][j+1] = 1;
}
}
for(int i=1; i<=r; i++) {
for(int j=1; j<=c; j++) {
n[i][j] += n[i-1][j] + n[i][j-1] - n[i-1][j-1];
}
}
for(int i=h; i<=r; i++) {
for(int j=w; j<=c; j++) {
if(n[i][j]-n[i-h][j]-n[i][j-w]+n[i-h][j-w] > (h*w)/2) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, vector<vector<int>> Q) {
r = R; c = C; h = H; w = W; v = Q;
int lo=1, hi=r*c+1;
while(lo < hi) {
int mid = (lo+hi)/2;
if(check(mid)) {
hi = mid;
} else {
lo = mid+1;
}
}
return lo;
}