Submission #996180

#	Time	Username	Problem	Language	Result	Execution time	Memory
996180		Yazan_SA	Quality Of Living (IOI10_quality)	C++14	100 / 100	979 ms	105720 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]) {
	vector<vector<int>>v(3001,vector<int>(3001));
	int l=1,r=R*C,bs;
	while(l<r){
		bs=(l+r)/2;
		bool is=0;
		for(int i=1; i<=R; i++)for(int j=1; j<=C; j++)
				v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+(Q[i-1][j-1]<=bs);
		for(int i=H; i<=R; i++)for(int j=W; j<=C; j++)
				is|=(v[i][j]-v[i-H][j]-v[i][j-W]+v[i-H][j-W]>=(H*W+1)/2);
		if(!is)l=bs+1;
		else r=bs;
	}
	return r;
}

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