| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 912805 | OAleksa | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "quality.h"
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int n = R, m = C;
int l = 1, r = n * m, ans = R * C;
vector<vector<int>> p(n, vector<int>(m));
auto Get = [&](int x1, int y1, int x2, int y2) {
int res = 0;
res += p[x2][y2];
if (x2 >= H)
res -= p[x2 - H][y2];
if (y2 >= W)
res -= p[x2][y2 - W];
if (x2 >= H && y2 >= W)
res += p[x2 - H][y2 - W];
return res;
};
auto check = [&](int mid) {
for (int i = 0;i < n;i++)
for (int j = 0;j < m;j++)
p[i][j] = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (Q[i][j] <= mid)
p[i][j]++;
if (i > 0 && j > 0)
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
else if (i > 0)
p[i][j] += p[i - 1][j];
else if (j > 0)
p[i][j] += p[i][j - 1];
}
}
int sz = H * W;
assert(sz % 2 == 1);
for (int i = 0;i + H < n;i++) {
for (int j = 0;j + W < m;j++) {
if (Get(i, j, i + H, j + W) >= (sz + 1) / 2)
return true;
}
}
return false;
};
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return ans;
}
// signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int tt = 1;
// //cin >> tt;
// while (tt--) {
// int r, c, h, w;
// cin >> r >> c >> h >> w;
// for (int i = 0;i < r;i++)
// for (int j = 0;j < c;j++)
// cin >> Q[i][j];
// cout << rectangle(r, c, h, w, Q) << '\n';
// }
// return 0;
// }