| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1090614 | namduong93 | 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.
/**
* author: namduong93
* created: unknown
* complexity: unknown
**/
#include <bits/stdc++.h>
using namespace std;
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdo(i, a, b) for (int i = a; i >= b; --i)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define SZ(x) ((int)(x).size())
int get_bit(int x, int i)
{
return x & (1 << i);
}
int turn_bit(int x, int i) { return x | (1 << i); }
int swap_bit(int x, int i) { return x ^ (1 << i); }
typedef pair<int, int> pii;
typedef long long ll;
const int mod = 998244353;
const int N = 3001;
const int inf = 1e9 + 7;
int n;
int R, C, H, W;
int a[N][N], tmp_Q[N][N], sum[N][N];
string str;
stack<int> st;
priority_queue<pii, vector<pii>, greater<pii>> d_heap;
multiset<int> ms;
int find(int m, int Q[3001][3001]) {
fto(i,1,R)
fto(j,1,C) {
if(Q[i][j] == m) tmp_Q[i][j] = 0;
if(Q[i][j] < m) tmp_Q[i][j] = -1;
if(Q[i][j] > m) tmp_Q[i][j] = 1;
}
fto(i,1,R) {
fto(j,1,C) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + tmp_Q[i][j];
}
}
bool exist = false;
fto(i,H,R) fto(j,W,C) {
int guess = sum[i][j] - sum[i - H][j] - sum[i][j - W] + sum[i - H][j - W];
if(guess < 0) return -1;
if (guess == 0) exist = true;
}
if(exist) return 0;
return 1;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int l = 1;
int r = R*C;
int result = -1;
while(l <= r) {
int m = (l + r) / 2;
int tmp = find(m, Q);
if(tmp == 0) {
result = m;
}
if(tmp <= 0) {
r = m - 1;
} else l = m + 1;
}
return result;
}
void Solve() {
cin >> R >> C >> H >> W;
fto(i,1,R) fto(j,1,C) {
cin>>a[i][j];
}
cout<<rectangle(R, C, H, W, a);
}
int32_t main()
{
if (fopen("test.inp", "r"))
freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int Test = 1;
// cin >> Test;
fto(iTest, 1, Test)
{
Solve();
}
// cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}