Submission #441720

#	Time	Username	Problem	Language	Result	Execution time	Memory
441720		dutch	Quality Of Living (IOI10_quality)	C++17	100 / 100	1949 ms	140200 KiB

quality

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

const int LIM = 3000;

int g[LIM+1][LIM+1];

int rectangle(int r, int c, int h, int w, int q[LIM+1][LIM+1]){
	int low = 1, high = r*c;
	while(low < high){
		int mid = (low + high) / 2;

		bool ok = 0;

		for(int i=0; i<r; ++i){
			for(int j=0; j<c; ++j){
				g[i+1][j+1] = q[i][j] <= mid ? 1 : -1;
				g[i+1][j+1] += g[i][j+1] + g[i+1][j] - g[i][j];
				if(i+1>=h && j+1>=w && g[i+1][j+1] + g[i+1-h][j+1-w]
					- g[i+1-h][j+1] - g[i+1][j+1-w] > 0) ok = 1;
			}
		}

		if(ok) high = mid;
		else low = mid + 1;
	}
	return low;
}

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