Submission #429214

#	Time	Username	Problem	Language	Result	Execution time	Memory
429214		dreezy	Quality Of Living (IOI10_quality)	C++17	100 / 100	2144 ms	175720 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
 
 
const int maxn = 3e3 + 5;


int prefsum[maxn][maxn];
int grid[maxn][maxn];
int r, c, h, w;
bool check(int x){
	memset(prefsum, 0, sizeof(prefsum));
	
	prefsum[0][0]=  grid[0][0] <=x ? 1: -1;

	for(int i =1; i<r; i++){
		prefsum[i][0] = grid[i][0] <= x ? 1: -1;
		prefsum[i][0] +=prefsum[i-1][0] ;	
	}
	
	for(int j =1; j<c; j++){
		prefsum[0][j] = grid[0][j] <= x ? 1: -1;
		prefsum[0][j] +=prefsum[0][j-1] ;	
	}
	
	
	for(int i = 1;i < r; i++){
		for(int j = 1; j< c;j++){
			prefsum[i][j] = grid[i][j]<= x ? 1: -1;
			 prefsum[i][j] += prefsum[i-1][j] + prefsum[i][j-1] - prefsum[i-1][j-1];
			
		}
	}
	
	/*if(x == 9){
		for(int i = 0;i < r; i++){
			for(int j = 0; j< c;j++){
				 cout << prefsum[i][j]<<" ";
		}
		cout <<endl;
		}
	}*/
	
	for(int top = 0; top <= r- h; top++){
		
		for(int left = 0; left <= c-w; left++ ){
			int val = prefsum[top + h -1] [left + w - 1];
			
			if(top > 0)
				val -= prefsum[top -1][left + w -1];
			if(left > 0)
				val -= prefsum[top + h -1][left - 1];
			if( top > 0 and left > 0)
				val += prefsum[top -1][left - 1];
			
			if(val > 0)
				return true;
		}
	}
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r = R;
	c = C;
	h = H;
	w = W;
	for(int i =0; i<r; i++)
		for(int j =0; j<c; j++)
			grid[i][j] = Q[i][j];

	int left = 1;
	int right = C * R;
	
	while(left != right){
		int mid = (left + right)/ 2;
		//cout << mid <<": "<<check(mid)<<endl;
		
		if(check(mid)){
			right = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return left;
 
}
 
/***********/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20