oj.uz

Submission #229149

# Submission time Handle Problem Language Result Execution time Memory
229149 2020-05-03T13:23:41 Z thtsshz_bgwrswh Quality Of Living (IOI10_quality) C++17
100 / 100
 3660 ms 175936 KB 
#pragma GCC optimize("Ofast")
#include "grader.h"
#include "quality.h"
#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 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 8 ms 1664 KB Output is correct
5 Correct 7 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 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 8 ms 1664 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5504 KB Output is correct
8 Correct 37 ms 5548 KB Output is correct
9 Correct 31 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 8 ms 1664 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5504 KB Output is correct
8 Correct 37 ms 5548 KB Output is correct
9 Correct 31 ms 5376 KB Output is correct
10 Correct 396 ms 30840 KB Output is correct
11 Correct 390 ms 30968 KB Output is correct
12 Correct 203 ms 21624 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 8 ms 1664 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 8 ms 1664 KB Output is correct
7 Correct 35 ms 5504 KB Output is correct
8 Correct 37 ms 5548 KB Output is correct
9 Correct 31 ms 5376 KB Output is correct
10 Correct 396 ms 30840 KB Output is correct
11 Correct 390 ms 30968 KB Output is correct
12 Correct 203 ms 21624 KB Output is correct
13 Correct 3660 ms 175936 KB Output is correct
14 Correct 3644 ms 175608 KB Output is correct
15 Correct 3387 ms 168472 KB Output is correct