oj.uz

Submission #429202

# Submission time Handle Problem Language Result Execution time Memory
429202 2021-06-15T18:53:58 Z dreezy Quality Of Living (IOI10_quality) C++17
0 / 100
 62 ms 35792 KB 
#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-1] = grid[0][j] <= x ? 1: -1;
		prefsum[0][j-1] +=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];
		}
	}
	
	
	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 > 1)
				val -= prefsum[top -1][left + w -1];
			if(left > 1)
				val -= prefsum[top + h -1][left - 1];
			if( top > 1 and left > 1)
				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;
		
		if(check(mid)){
			right = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return left;
 
}
 
/***********/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35788 KB Output is correct
2 Incorrect 62 ms 35792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35788 KB Output is correct
2 Incorrect 62 ms 35792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35788 KB Output is correct
2 Incorrect 62 ms 35792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35788 KB Output is correct
2 Incorrect 62 ms 35792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35788 KB Output is correct
2 Incorrect 62 ms 35792 KB Output isn't correct
3 Halted 0 ms 0 KB -