Submission #595779

#	Time	Username	Problem	Language	Result	Execution time	Memory
595779		fuad27	Quality Of Living (IOI10_quality)	C++17	100 / 100	1601 ms	106356 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
long long pref[3010][3010];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int lo = -1, hi = R*C;
	while(hi-lo>1) {
		int mid = (lo+hi)/2;
		for(int i = 0;i<R;i++)pref[i][0]=0;
		for(int i = 0;i<C;i++)pref[0][i]=0;
		for(int i = 1;i<=R;i++) {
			for(int j = 1;j<=C;j++) {
				pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(Q[i-1][j-1]<=mid);
			}
		}
		bool check=false;
		for(int i = H;i<=R;i++) {
			for(int j = W;j<=C;j++) {
				if((pref[i][j]-pref[i-H][j]+pref[i-H][j-W]-pref[i][j-W])>(H*W)/2)check=true;
			}
		}
		if(check) {
			hi=mid;
		}
		else {
			lo=mid;
		}
	}
	return hi;
}

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