Submission #805259

#	Time	Username	Problem	Language	Result	Execution time	Memory
805259		QwertyPi	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	468 KiB

quality

#pragma once

int ps[3001][3001];
int sum(int x1, int x2, int y1, int y2){
	return ps[x2 + 1][y2 + 1] - ps[x2 + 1][y1] - ps[x1][y2 + 1] + ps[x1][y1];
}

int ok(int R, int C, int H, int W, int Q[3001][3001], int x){
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			ps[i + 1][j + 1] = ps[i + 1][j] + ps[i][j + 1] - ps[i][j] + (Q[i][j] < x);
		}
	}
	for(int i = 0; i <= R - H; i++){
		for(int j = 0; j <= C - W; j++){
			if(sum(i, i + H - 1, j, j + C - 1) >= H * W / 2){
				return true;
			}
		}
	}
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
	int lo = 1, hi = R * C;
	while(lo != hi){
		int mid = (lo + hi) / 2;
		if(ok(R, C, H, W, Q, mid)){
			hi = mid;
		}else{
			lo = mid + 1;
		}
	}
	return lo;
}

Compilation message (stderr)

quality.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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