oj.uz

Submission #587365

# Submission time Handle Problem Language Result Execution time Memory
587365 2022-07-01T17:28:43 Z HeyYouNotYouYou Quality Of Living (IOI10_quality) C++14
100 / 100
 1969 ms 175276 KB 
#include "quality.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

	int n = R , m = C;
	int l = 1 , r = R*C, ans = R*C;
	while(l<=r)
	{
		int mid = (l+r)/2;
		//cout<<mid<<endl;
		int less[n+1][m+1]={0} , more[n+1][m+1]={0},cursmall=0,curbig=0;
		memset(less,0,sizeof less);
		memset(more,0,sizeof more);
		for(int i = 1 ; i <= n ; i ++)
		{
			for(int j = 1 ; j <= m ; j ++)
			{
				less[i][j] = less[i-1][j] + less[i][j-1] - less[i-1][j-1] + (Q[i-1][j-1]<mid);
				more[i][j] = more[i-1][j] + more[i][j-1] - more[i-1][j-1] + (Q[i-1][j-1]>mid);

			}
		}

		int ok = 0;
		for(int i = 1 ; i <= n-H+1 ; i ++)
		{
			for(int j = 1 ; j <= m-W+1 ; j ++)
			{
				//cout<<mid<<" "<<i+H-1<<" "<<j+W-1<<endl;
				int olayel = less[i+H-1][j+W-1] - less[i-1][j+W-1] - less[i+H-1][j-1] + less[i-1][j-1];
				int kteer = more[i+H-1][j+W-1] - more[i-1][j+W-1] - more[i+H-1][j-1] + more[i-1][j-1];
				if(olayel == kteer  && olayel == (H*W)/2) {
					//cout<<"!"<<i<<" "<<j<<" "<<olayel<<" "<<kteer<<endl;
					ans=min(ans,mid),ok=1;
				}
				if(olayel >= kteer) ok=1;
			}
		}

		if(ok){
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:13:47: warning: unused variable 'cursmall' [-Wunused-variable]
   13 |   int less[n+1][m+1]={0} , more[n+1][m+1]={0},cursmall=0,curbig=0;
      |                                               ^~~~~~~~
quality.cpp:13:58: warning: unused variable 'curbig' [-Wunused-variable]
   13 |   int less[n+1][m+1]={0} , more[n+1][m+1]={0},cursmall=0,curbig=0;
      |                                                          ^~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 15 ms 3000 KB Output is correct
8 Correct 16 ms 3012 KB Output is correct
9 Correct 13 ms 2944 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 15 ms 3000 KB Output is correct
8 Correct 16 ms 3012 KB Output is correct
9 Correct 13 ms 2944 KB Output is correct
10 Correct 195 ms 22804 KB Output is correct
11 Correct 188 ms 22772 KB Output is correct
12 Correct 90 ms 13464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 15 ms 3000 KB Output is correct
8 Correct 16 ms 3012 KB Output is correct
9 Correct 13 ms 2944 KB Output is correct
10 Correct 195 ms 22804 KB Output is correct
11 Correct 188 ms 22772 KB Output is correct
12 Correct 90 ms 13464 KB Output is correct
13 Correct 1969 ms 154560 KB Output is correct
14 Correct 1906 ms 175276 KB Output is correct
15 Correct 1818 ms 161128 KB Output is correct