Submission #403979

#	Time	Username	Problem	Language	Result	Execution time	Memory
403979		Antekb	Quality Of Living (IOI10_quality)	C++14	100 / 100	3091 ms	166500 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int tab[R][C];
	vector<int> V;
	for(int i=0; i<R; i++){
		for(int j=0; j<C; j++){
			V.push_back(Q[i][j]);
		}
	}
	sort(V.begin(), V.end());
	int l=0, r=V.size()-1;
	while(l<r){
		bool b=0;
		int m=(l+r+1)>>1;
		int k=V[m];
		//cerr<<V[m]<<"\n";
		for(int i=0; i<R; i++){
			for(int j=0; j<C; j++){
				tab[i][j]=(Q[i][j]<k);
				//cout<<tab[i][j]<<" ";
			}
			//cout<<"\n";
		}
		for(int i=0; i<R; i++){
			for(int j=0; j<C; j++){
				if(i)tab[i][j]+=tab[i-1][j];
				if(j)tab[i][j]+=tab[i][j-1];
				if(i && j)tab[i][j]-=tab[i-1][j-1];
				//cout<<tab[i][j]<<" ";
				if(i>=H-1 && j>=W-1){
					int t=tab[i][j];
					if(i>=H)t-=tab[i-H][j];
					if(j>=W)t-=tab[i][j-W];
					if(i>=H && j>=W)t+=tab[i-H][j-W];
					if(t>H*W/2)b=1;
				}
			}
			//cout<<"\n";
		}
		//cerr<<b<<"\n";
		if(b)r=m-1;
		else l=m;
	}
	return V[l];
}

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