Submission #1013685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013685		Nonoze	Quality Of Living (IOI10_quality)	C++17	100 / 100	3050 ms	140324 KiB

quality

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

int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
	int ans=n*m, l=1, r=n*m;
	while (l<=r) {
		int mid=(l+r)/2;
		vector<vector<int>> x(n, vector<int>(m, 0));
		for (int i=0; i<n; i++) {
			queue<int> q;
			for (int j=m-1; j>=0; j--) {
				if (a[i][j]<=mid) q.push(j);
				if (!q.empty() && q.front()-j>=w) q.pop();
				x[i][j]=(int)q.size();
			}
		}
		int res=0;
		for (int j=0; j<m; j++) {
			int sum=0;
			for (int i=n-1; i>=0; i--) {
				if (i+h<n) sum-=x[i+h][j];
				sum+=x[i][j];
				res=max(res, sum);
			}
		}
		if (res>(h*w/2)) ans=mid, r=mid-1;
		else l=mid+1;
	}
	return ans;
}

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