| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482392 | HoangVu | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//ifstream f1("test.inp");
//ofstream f2("test.out");
//#define cin f1
//#define cout f2
inline void in(int &x) // fast input
{
x = 0; long long f = 1;
char ch = getchar();
while (!isdigit(ch)) f = ch == '-' ? - f : f, ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
x *= f;
}
inline void out(int _x){
char _str[16];
long long _i=0;
if (_x==0) putchar('0');
else{
while (_x>0){ _str[_i++]=(_x%10)+'0'; _x=_x/10; }
while (_i) putchar(_str[--_i]); }
putchar('\n');
}
int numRow, numColumn, a[3005][3005], H, W;
int x[3005][3005], pref[3005][3005];
int getValue(int x, int y, int u, int v) {
return pref[u][v] - pref[x - 1][v] - pref[u][y - 1] + pref[x - 1][y - 1];
}
bool ok(int need) {
for (int i = 1; i <= numRow; i++) {
for (int j = 1; j <= numColumn; j++) {
if (a[i][j] >= need) pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + 1;
else pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] - 1;
}
}
for (int i = 1; i + H - 1 <= numRow; i++)
for (int j = 1; j + W - 1 <= numColumn; j++)
if (getValue(i, j, i + H - 1, j + W - 1) > 0)
return true;
return false;
}
void solve() {
in(numRow), in(numColumn), in(H), in(W);
//cin >> numRow >> numColumn >> H >> W;
for (int i = 1; i <= numRow; i++)
for (int j = 1; j <= numColumn; j++)
in(a[i][j]);
int L = 1, R = numRow * numColumn;
while (L <= R) {
int mid = (L + R) >> 1;
if (ok(mid)) L = mid + 1;
else R = mid - 1;
}
cout << --L;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}