Submission #1012543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012543		Ludissey	Quality Of Living (IOI10_quality)	C++14	100 / 100	1899 ms	175636 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;

vector<vector<int>> a;

int R,C,H,W;

int f(int x){
	vector<vector<int>> pref(R, vector<int>(C,0));
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if(a[i][j]<x) pref[i][j]--;
			if(a[i][j]>x) pref[i][j]++;
			if(i>0) pref[i][j]+=pref[i-1][j];
			if(j>0) pref[i][j]+=pref[i][j-1];
			if(j>0&&i>0) pref[i][j]-=pref[i-1][j-1];
			//cerr << pref[i][j] << " ";
		}
		//cerr << "\n";
	}

	int mn=1;
	for (int i = H-1; i < R; i++)
	{
		for (int j = W-1; j < C; j++)
		{
			int sm=pref[i][j];
			if(i>=H) sm-=pref[i-H][j];
			if(j>=W) sm-=pref[i][j-W];
			if(i>=H&&j>=W) sm+=pref[i-H][j-W];
			if(sm<0) sm=-1;
			else sm=min(1,sm);
			mn=min(sm,mn);
		}
	}
	return mn;
}

int rectangle(int _R, int _C, int _H, int _W, int Q[3001][3001]) {
	R=_R;
	C=_C;
	H=_H;
	W=_W;
	a.resize(R, vector<int>(C));
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			a[i][j]=Q[i][j];
		}
	}
	int l=1; int r=R*C;
	while(l<r){
		int mid=(l+r)/2;
		int ff=f(mid);
		if(ff==0){
			l=mid;
			break; 
		}else if(ff<0) {
			r=mid;
		}else{
			l=mid+1;
		}
	}
	return l;
}

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