Submission #1263971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263971		liangjeremy	Quality Of Living (IOI10_quality)	C++20	100 / 100	2635 ms	247448 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using db=double;
using sll=__int128;
using lb=long double;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
#define int long long
	int r=R; int c=C; int h=H; int w=W; 
	vector<vector<int>>a(r+1,vector<int>(c+1));
	for(int i=1; i<=r; i++){
		for(int j=1; j<=c; j++){
			a[i][j]=Q[i-1][j-1]; 
		}
	}
	int left=1; int right=r*c;
	while(left<right){
		int mid=(left+right)>>1; vector<vector<int>>v(r+1,vector<int>(c+1)); vector<vector<int>>prefix(r+1,vector<int>(c+1)); 
		for(int i=1; i<=r; i++){
			for(int j=1; j<=c; j++){
				v[i][j]=(a[i][j]<=mid); prefix[i][j]=v[i][j]+prefix[i][j-1]+prefix[i-1][j]-prefix[i-1][j-1]; 
			}
		}
		int mx=0;
		for(int i=1; i+h-1<=r; i++){
			for(int j=1; j+w-1<=c; j++){
				int x1=i; int y1=j; int x2=i+h-1; int y2=j+w-1; 
				mx=max(mx,prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][y1-1]);
			}
		}
		if(mx>=(h*w)/2+1)right=mid; else left=mid+1; 
	}
#undef int
	return (int)left; 
}

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