| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 241555 | davi_bart | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int x[3001][3001];
bool c(int k,int R,int C,int H,int W,int Q[3001][3001]){
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
x[i][j]=0;
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
x[i][j]=Q[i][j]<k;
if(Q[i][j]==k)x[i][j]+=100000000;
if(j>0)x[i][j]+=x[i][j-1];
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(i>0)x[i][j]+=x[i-1][j];
}
}
for(int i=H-1;i<R;i++){
for(int j=W-1;j<C;j++){
int z=x[i][j];
if(i>H-1)z-=x[i-H][j];
if(j>W-1)z-=x[i][j-W];
if(i>=H && j>=W)z+=x[i-H][j-W];
if(z>=(H*W/2)+100000000){
return 1;
}
}
}
return 0;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
int l=1,r=R*C+1;
while(l<r-1){
int m=(l+r)/2;
if(c(m,R,C,H,W,Q))r=m;
else l=m;
}
return l+1;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int R,C,H,W;
cin>>R>>C>>H>>W;
int Q[3001][3001];
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);
}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/