Submission #1075341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075341		LCJLY	Quality Of Living (IOI10_quality)	C++14	100 / 100	1086 ms	175708 KiB

quality

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

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=0;
	int r=R*C;
	int mid;
	int best=r;
	while(l<=r){
		mid=(l+r)/2;
		int arr[R+5][C+5];
		int dp[R+5][C+5];
		memset(dp,0,sizeof(dp));
		//show(mid,mid);
		for(int x=1;x<=R;x++){
			for(int y=1;y<=C;y++){
				arr[x][y]=(Q[x-1][y-1]<=mid);
				dp[x][y]=dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1]+arr[x][y];
				//cout << arr[x][y] << " ";
			}
			//cout << "\n";
		}
		
		int maxi=0;
		for(int x=H;x<=R;x++){
			for(int y=W;y<=C;y++){
				maxi=max(maxi,dp[x][y]-dp[x][y-W]-dp[x-H][y]+dp[x-H][y-W]);
			}
		}
		if(maxi>H*W/2){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return best;
}

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