Submission #1029904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029904		Tob	Quality Of Living (IOI10_quality)	C++14	100 / 100	1046 ms	140200 KiB

quality

#include <bits/stdc++.h>

#include "quality.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

int ps[3001][3001];
int rectangle(int n, int m, int h, int w, int Q[3001][3001]) {
	int lo = 1, hi = n*m;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		memset(ps, 0, sizeof ps);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				ps[i+1][j+1] = ps[i][j+1] + ps[i+1][j] - ps[i][j] + (Q[i][j] <= mid);
			}
		}
		int ok = 0;
		for (int i = h; i <= n; i++) {
			for (int j = w; j <= m; j++) {
				if (ps[i][j] - ps[i-h][j] - ps[i][j-w] + ps[i-h][j-w] > h*w/2) ok = 1;
			}
		}
		if (ok) hi = mid;
		else lo = mid+1;
	}
	return lo;
}
/*
static int R,C,H,W,Q[3001][3001],i,j,ans;
int main(){
   scanf("%d%d%d%d",&R,&C,&H,&W);
   for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
   ans = rectangle(R,C,H,W,Q);
   printf("%d\n",ans);
   return 0;
}*/

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