| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 912805 | OAleksa | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
// }