oj.uz

Submission #595931

# Submission time Handle Problem Language Result Execution time Memory
595931 2022-07-14T08:10:45 Z BT21tata Quality Of Living (IOI10_quality) C++17
100 / 100
 2045 ms 108372 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;

int cnt[3005][3005], q[3005][3005];

bool check(int num, int r, int c, int h, int w)
{
	//cout<<num<<endl;
	memset(cnt, 0, sizeof(cnt));
	for(int i=1; i<=r; i++)
		for(int j=1; j<=c; j++)
		{
			//cout<<cnt[i-1][j]<<' '<<cnt[i][j-1]<<' '<<cnt[i-1][j-1]<<' '<<q[i][j]<<' '<<(q[i][j]<num)<<endl;
			cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+(q[i][j]<=num)/*, cout<<i<<' '<<j<<' '<<cnt[i][j]<<endl*/;
		}
	
	for(int i=1; i<=r; i++)
	{
		for(int j=1; j<=c; j++)
		{
			if(i+h-1>r) continue;
			if(j+w-1>c) continue;
			int sum=cnt[i+h-1][j+w-1]-cnt[i-1][j+w-1]-cnt[i+h-1][j-1]+cnt[i-1][j-1];
			//cout<<"sum  "<<i<<' '<<j<<' '<<sum<<endl;
			if(sum>h*w/2) return 1;
		}
	}
	return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
	int l=1, r=R*C, mid;
	for(int i=0; i<R; i++)
	{
		for(int j=0; j<C; j++)
		{
			q[i+1][j+1]=Q[i][j];
		}
	}
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid, R, C, H, W)) r=mid-1;
		else l=mid+1;
	}
	return l;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 35888 KB Output is correct
2 Correct 54 ms 35884 KB Output is correct
3 Correct 49 ms 35880 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 35888 KB Output is correct
2 Correct 54 ms 35884 KB Output is correct
3 Correct 49 ms 35880 KB Output is correct
4 Correct 66 ms 36560 KB Output is correct
5 Correct 62 ms 36564 KB Output is correct
6 Correct 63 ms 36568 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 35888 KB Output is correct
2 Correct 54 ms 35884 KB Output is correct
3 Correct 49 ms 35880 KB Output is correct
4 Correct 66 ms 36560 KB Output is correct
5 Correct 62 ms 36564 KB Output is correct
6 Correct 63 ms 36568 KB Output is correct
7 Correct 99 ms 39276 KB Output is correct
8 Correct 90 ms 39244 KB Output is correct
9 Correct 88 ms 39156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 35888 KB Output is correct
2 Correct 54 ms 35884 KB Output is correct
3 Correct 49 ms 35880 KB Output is correct
4 Correct 66 ms 36560 KB Output is correct
5 Correct 62 ms 36564 KB Output is correct
6 Correct 63 ms 36568 KB Output is correct
7 Correct 99 ms 39276 KB Output is correct
8 Correct 90 ms 39244 KB Output is correct
9 Correct 88 ms 39156 KB Output is correct
10 Correct 279 ms 54304 KB Output is correct
11 Correct 335 ms 54388 KB Output is correct
12 Correct 176 ms 50372 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 35888 KB Output is correct
2 Correct 54 ms 35884 KB Output is correct
3 Correct 49 ms 35880 KB Output is correct
4 Correct 66 ms 36560 KB Output is correct
5 Correct 62 ms 36564 KB Output is correct
6 Correct 63 ms 36568 KB Output is correct
7 Correct 99 ms 39276 KB Output is correct
8 Correct 90 ms 39244 KB Output is correct
9 Correct 88 ms 39156 KB Output is correct
10 Correct 279 ms 54304 KB Output is correct
11 Correct 335 ms 54388 KB Output is correct
12 Correct 176 ms 50372 KB Output is correct
13 Correct 2045 ms 108356 KB Output is correct
14 Correct 1944 ms 108372 KB Output is correct
15 Correct 1953 ms 108164 KB Output is correct