| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 683460 | slo | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))
typedef long long ll;
typedef unsigned long long int ull;
typedef pair<int,int> ii;
typedef pair<int,ll> ill;
typedef pair<ll,int> lli;
typedef pair<ll,ll> lll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps=1e-9;
if(x+eps<y){
x=y; return true;
}
return false;
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps=1e-9;
if(x>y+eps){
x=y; return true;
}
return false;
}
/*-----------------MAIN PROGRAM-----------------*/
const int SZ=3001;
int r, c ,h, w;
int a[SZ][SZ], b[SZ][SZ];
void read(){
cin>>r>>c>>h>>w;
fore(i,1,r) fore(j,1,c) cin>>a[i][j];
}
bool good(int med){
fore(i,1,r) fore(j,1,c){
if(a[i][j]>med) b[i][j]=1;
else if(a[i][j]<med) b[i][j]=-1;
else b[i][j]=0;
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
fore(i,1,r-h+1) fore(j,1,c-w+1){
int tot=b[i+h-1][j+w-1]-b[i+h-1][j-1]
-b[i-1][j+w-1]+b[i-1][j-1];
if(tot<=0) return true;
}
return false;
}
int rectangle(int r, int c, int h, int w, int a[][SZ]){
int left=1, right=r*c, ans=1;
while(left<=right){
int m=(left+right)/2;
if(good(m)){
ans=m;
right=m-1;
}
else left=m+1;
}
return ans;
}
int main(){
fastIO;
read();
cout<<rectangle(r,c,h,w,a)<<'\n';
return 0;
}