제출 #1267081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267081		herominhsteve	삶의 질 (IOI10_quality)	C++20	100 / 100	1146 ms	71008 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3001;

int rectangle(int n,int m,int H,int W, int grid[MAXN][MAXN]){
	int l=1, r = n * m;
	int res = r;
	vector<vector<int>> pre(n,vector<int>(m,0));

	function<bool(int)>  check = [&] (int mid) -> bool {
		for (int i=0;i<n;i++){
			for (int j=0;j<m;j++){
				int cur = (grid[i][j] <= mid ? 1 : -1);
				int upperHalf = (!i ? 0 : pre[i-1][j]);
				int leftHalf = (!j ? 0 : pre[i][j-1]);
				int overlap = ((i and j) ? pre[i-1][j-1] : 0);
				pre[i][j] = upperHalf + leftHalf - overlap + cur;
			}
		}
		for (int i = H-1; i < n; i++) {
			for (int j = W-1; j < m; j++) {
				int cur = pre[i][j]
						- (i-H >= 0 ? pre[i-H][j] : 0)
						- (j-W >= 0 ? pre[i][j-W] : 0)
						+ (i-H >= 0 and j-W >= 0 ? pre[i-H][j-W] : 0);
				if (cur > 0) return true;
			}
		}
		return false;
	};

	while (l<=r){
		int mid = (l+r)>>1;
		if (check(mid)){
			res = mid;
			r=mid-1;
		} else{
			l = mid + 1;
		}
	}
	return res;
}

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