Submission #287366

#	Time	Username	Problem	Language	Result	Execution time	Memory
287366		Namnamseo	Quality Of Living (IOI10_quality)	C++17	100 / 100	2448 ms	135180 KiB

quality

int n,m;
int p,q;
int (*data)[3001];
int small[3010][3010];
int big  [3010][3010];
inline int get(int array[][3010],int x,int y){
    return array[x][y]-array[x][y-q]-array[x-p][y]+array[x-p][y-q];
}
bool test(int x){
    int i,j;
    for(i=1;i<=n;++i) for(j=1;j<=m;++j){
        small[i][j]=small[i][j-1]+small[i-1][j]-small[i-1][j-1]+(data[i-1][j-1]<x);
        big  [i][j]=big  [i][j-1]+big  [i-1][j]-big  [i-1][j-1]+(data[i-1][j-1]>x);
    }
    for(i=p;i<=n;++i) for(j=q;j<=m;++j){
         if(get(small,i,j)>=get(big,i,j)) {
            return true;
         }
    }
    return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
  	n = R; m = C; p = H; q = W; data = Q;
    int i,j;
    i=p*q/2; j=n*m+1;
    int mid;
    while(i+1<j){
        mid=(i+j)/2;
        (test(mid)?j:i)=mid;
    }
    return j;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20