oj.uz

Submission #287366

# Submission time Handle Problem Language Result Execution time Memory
287366 2020-08-31T16:31:20 Z Namnamseo Quality Of Living (IOI10_quality) C++17
100 / 100
 2448 ms 135180 KB 
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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 23 ms 5496 KB Output is correct
8 Correct 23 ms 5496 KB Output is correct
9 Correct 46 ms 5368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 23 ms 5496 KB Output is correct
8 Correct 23 ms 5496 KB Output is correct
9 Correct 46 ms 5368 KB Output is correct
10 Correct 279 ms 30772 KB Output is correct
11 Correct 259 ms 30772 KB Output is correct
12 Correct 160 ms 21496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 23 ms 5496 KB Output is correct
8 Correct 23 ms 5496 KB Output is correct
9 Correct 46 ms 5368 KB Output is correct
10 Correct 279 ms 30772 KB Output is correct
11 Correct 259 ms 30772 KB Output is correct
12 Correct 160 ms 21496 KB Output is correct
13 Correct 2448 ms 117752 KB Output is correct
14 Correct 2445 ms 135180 KB Output is correct
15 Correct 2268 ms 132420 KB Output is correct