oj.uz

Submission #545242

# Submission time Handle Problem Language Result Execution time Memory
545242 2022-04-04T04:57:03 Z AbdelmagedNour Quality Of Living (IOI10_quality) C++17
100 / 100
 1702 ms 106080 KB 
#include<bits/stdc++.h>
#include "quality.h"
//#include "grader.cpp"
int a[3001][3001],pre[3001][3001];
int n,m,x,y;
int sum(int x1,int x2,int y1,int y2){
    int sum1=pre[x2][y2];
    int sum2=(y1?pre[x2][y1-1]:0);
    int sum3=(x1?pre[x1-1][y2]:0);
    int sum4=(x1&&y1?pre[x1-1][y1-1]:0);
    return sum1-sum2-sum3+sum4;
}
bool f(int X){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            pre[i][j]=(i?pre[i-1][j]:0)+(j?pre[i][j-1]:0)-(i&&j?pre[i-1][j-1]:0)+(a[i][j]<=X?1:-1);
        }
    }
    for(int i=x-1;i<n;i++){
        for(int j=y-1;j<m;j++){
            if(sum(i-x+1,i,j-y+1,j)>=1){
                return 1;
            }
        }
    }
    return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	n=R;m=C;x=H;y=W;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=Q[i][j];
	int l=1,r=n*m,res=INT_MAX;
	while(l<=r){
        int md=(l+r)>>1;
        if(f(md))r=(res=md)-1;
        else l=md+1;
	}
	return res;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 4 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 16 ms 4956 KB Output is correct
9 Correct 14 ms 4872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 4 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 16 ms 4956 KB Output is correct
9 Correct 14 ms 4872 KB Output is correct
10 Correct 184 ms 24056 KB Output is correct
11 Correct 178 ms 24092 KB Output is correct
12 Correct 102 ms 18128 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 4 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 16 ms 4956 KB Output is correct
9 Correct 14 ms 4872 KB Output is correct
10 Correct 184 ms 24056 KB Output is correct
11 Correct 178 ms 24092 KB Output is correct
12 Correct 102 ms 18128 KB Output is correct
13 Correct 1702 ms 106000 KB Output is correct
14 Correct 1578 ms 106080 KB Output is correct
15 Correct 1523 ms 106024 KB Output is correct