oj.uz

Submission #229151

# Submission time Handle Problem Language Result Execution time Memory
229151 2020-05-03T13:24:32 Z thtsshz_bgwrswh Quality Of Living (IOI10_quality) C++17
100 / 100
 3610 ms 106312 KB 
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<algorithm>
using namespace std;
int r,c,h,w,num[3005][3005],pre[3005][3005];
bool check(int v){
	int i,j;
	for(i=0;i<r;i++){
		for(j=0;j<c;j++){
			if(num[i][j]<v)
				pre[i][j]=1;
			else if(num[i][j]==v)
				pre[i][j]=0;
			else
				pre[i][j]=-1; 
		}
	}
	for(i=0;i<r;i++)
		for(j=0;j<c;j++)
			pre[i][j]+=(j?pre[i][j-1]:0)+(i?pre[i-1][j]:0)-((i&&j)?pre[i-1][j-1]:0);
	for(i=0;i<=r-h;i++)
		for(j=0;j<=c-w;j++)
			if(pre[i+h-1][j+w-1]+((i&&j)?pre[i-1][j-1]:0)-(j?pre[i+h-1][j-1]:0)-(i?pre[i-1][j+w-1]:0)>=0)
				return 1;
	return 0;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
	r=R;
	c=C;
	h=H;
	w=W;
	int i,j,right=r*c+1,left=0;
	for(i=0;i<r;i++)
		for(j=0;j<c;j++)
			num[i][j]=Q[i][j];
	while(right-left>1){
		int mid=(right+left)>>1;
		if(check(mid))
			right=mid;
		else
			left=mid;		
	}
	return right;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 7 ms 1664 KB Output is correct
5 Correct 8 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5532 KB Output is correct
8 Correct 34 ms 5504 KB Output is correct
9 Correct 32 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 7 ms 1664 KB Output is correct
5 Correct 8 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5532 KB Output is correct
8 Correct 34 ms 5504 KB Output is correct
9 Correct 32 ms 5376 KB Output is correct
10 Correct 383 ms 24824 KB Output is correct
11 Correct 371 ms 24920 KB Output is correct
12 Correct 190 ms 19192 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 7 ms 1664 KB Output is correct
5 Correct 8 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5532 KB Output is correct
8 Correct 34 ms 5504 KB Output is correct
9 Correct 32 ms 5376 KB Output is correct
10 Correct 383 ms 24824 KB Output is correct
11 Correct 371 ms 24920 KB Output is correct
12 Correct 190 ms 19192 KB Output is correct
13 Correct 3610 ms 106312 KB Output is correct
14 Correct 3563 ms 106248 KB Output is correct
15 Correct 3309 ms 106288 KB Output is correct