# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
595776 | snasibov05 | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "quality.h"
#include "bits/stdc++.h"
bool check(int k, int r, int c, int h, int w, int q[3001][3001]){
vector<vector<int>> cntp(r, vector<int>(c));
for (int i = 0; i < r; ++i){
for (int j = 0; j < c; ++j){
if (i != 0) cntp[i][j] += cntp[i-1][j];
if (j != 0) cntp[i][j] += cntp[i][j-1];
if (i != 0 && j != 0) cntp[i][j] -= cntp[i-1][j-1];
cntp[i][j] += q[i][j] <= k;
}
}
for (int i = h-1; i < r; ++i){
for (int j = w-1; j < c; ++j){
int cnt = cntp[i][j];
if (i != h-1) cnt -= cntp[i - h][j];
if (j != w-1) cnt -= cntp[i][j - w];
if (i != h-1 && j != w-1) cnt += cntp[i - h][j - w];
if (cnt > h * w / 2) return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 1, r = R*C;
int bst = 0;
while (l <= r){
int mid = (l + r) / 2;
if (check(mid, R, C, H, W, Q)) bst = mid, r = mid - 1;
else l = mid + 1;
}
return bst;
}