oj.uz

Submission #512652

# Submission time Handle Problem Language Result Execution time Memory
512652 2022-01-16T15:32:49 Z algorithm16 Quality Of Living (IOI10_quality) C++14
100 / 100
 1515 ms 89364 KB 
#include "quality.h"
int sum[3005][3005];
int get_sum(int x1,int y1,int x2,int y2) {
	int ret=sum[x2][y2];
	if(x1) ret-=sum[x1-1][y2];
	if(y1) ret-=sum[x2][y1-1];
	if(x1 && y1) ret+=sum[x1-1][y1-1];
	return ret;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int r=R,c=C,h=H,w=W;
	int lo=1,hi=r*c;
	while(lo<hi) {
		int mid=(lo+hi)/2;
		int s=0,cnt=0;
		for(int i=0;i<r;i++) {
			s=0;
			for(int j=0;j<c;j++) {
				if(Q[i][j]<=mid) s+=1;
				else s-=1;
				sum[i][j]=s;
				if(i) sum[i][j]+=sum[i-1][j];
			}
		}
		for(int i=0;i+h-1<r;i++) {
			for(int j=0;j+w-1<c;j++) {
				if(get_sum(i,j,i+h-1,j+w-1)>0) cnt+=1;
			}
		}
		if(cnt) hi=mid;
		else lo=mid+1;
	}
	return lo;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 2 ms 1188 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 2 ms 1188 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 13 ms 3816 KB Output is correct
8 Correct 14 ms 3880 KB Output is correct
9 Correct 13 ms 3788 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 2 ms 1188 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 13 ms 3816 KB Output is correct
8 Correct 14 ms 3880 KB Output is correct
9 Correct 13 ms 3788 KB Output is correct
10 Correct 190 ms 22744 KB Output is correct
11 Correct 177 ms 22812 KB Output is correct
12 Correct 78 ms 15428 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 2 ms 1188 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 13 ms 3816 KB Output is correct
8 Correct 14 ms 3880 KB Output is correct
9 Correct 13 ms 3788 KB Output is correct
10 Correct 190 ms 22744 KB Output is correct
11 Correct 177 ms 22812 KB Output is correct
12 Correct 78 ms 15428 KB Output is correct
13 Correct 1515 ms 89364 KB Output is correct
14 Correct 1446 ms 89356 KB Output is correct
15 Correct 1343 ms 87988 KB Output is correct