Submission #1267091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267091		herominhsteve	Quality Of Living (IOI10_quality)	C++20	100 / 100	1147 ms	106372 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

const int MAXN = 3001;

int rectangle(int n,int m,int H,int W, int Q[MAXN][MAXN]){
	vector<vector<int>> pre(n+1,vector<int>(m+1,0));
	vector<vector<int>> grid(n+1,vector<int>(m+1,0));
	
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			grid[i+1][j+1] = Q[i][j];
		}
	}

	int l=1, r = n * m;
	int res = r;

	function<bool(int)>  check = [&] (int mid) -> bool {
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (grid[i][j] <= mid ? 1 : -1);
			}
		}
		for (int i=H;i<=n;i++){
			for (int j=W;j<=m;j++){
				int val = pre[i][j] - pre[i-H][j] - pre[i][j-W] + pre[i-H][j-W];
				if (val>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