oj.uz

답안 #429214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429214 2021-06-15T19:03:04 Z dreezy 삶의 질 (IOI10_quality) C++17
100 / 100
 2144 ms 175720 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] = 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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 35788 KB Output is correct
2 Correct 53 ms 35876 KB Output is correct
3 Correct 51 ms 35876 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 35788 KB Output is correct
2 Correct 53 ms 35876 KB Output is correct
3 Correct 51 ms 35876 KB Output is correct
4 Correct 65 ms 36556 KB Output is correct
5 Correct 66 ms 36556 KB Output is correct
6 Correct 66 ms 36552 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 35788 KB Output is correct
2 Correct 53 ms 35876 KB Output is correct
3 Correct 51 ms 35876 KB Output is correct
4 Correct 65 ms 36556 KB Output is correct
5 Correct 66 ms 36556 KB Output is correct
6 Correct 66 ms 36552 KB Output is correct
7 Correct 103 ms 39260 KB Output is correct
8 Correct 97 ms 39264 KB Output is correct
9 Correct 94 ms 39116 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 35788 KB Output is correct
2 Correct 53 ms 35876 KB Output is correct
3 Correct 51 ms 35876 KB Output is correct
4 Correct 65 ms 36556 KB Output is correct
5 Correct 66 ms 36556 KB Output is correct
6 Correct 66 ms 36552 KB Output is correct
7 Correct 103 ms 39260 KB Output is correct
8 Correct 97 ms 39264 KB Output is correct
9 Correct 94 ms 39116 KB Output is correct
10 Correct 320 ms 58224 KB Output is correct
11 Correct 300 ms 58188 KB Output is correct
12 Correct 206 ms 50860 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 35788 KB Output is correct
2 Correct 53 ms 35876 KB Output is correct
3 Correct 51 ms 35876 KB Output is correct
4 Correct 65 ms 36556 KB Output is correct
5 Correct 66 ms 36556 KB Output is correct
6 Correct 66 ms 36552 KB Output is correct
7 Correct 103 ms 39260 KB Output is correct
8 Correct 97 ms 39264 KB Output is correct
9 Correct 94 ms 39116 KB Output is correct
10 Correct 320 ms 58224 KB Output is correct
11 Correct 300 ms 58188 KB Output is correct
12 Correct 206 ms 50860 KB Output is correct
13 Correct 2144 ms 175720 KB Output is correct
14 Correct 2092 ms 175536 KB Output is correct
15 Correct 1982 ms 168416 KB Output is correct