Submission #237386

#	Time	Username	Problem	Language	Result	Execution time	Memory
237386		kshitij_sodani	Quality Of Living (IOI10_quality)	C++17	100 / 100	3456 ms	128048 KiB

quality

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "quality.h"
int n,m,aa,bb;
int it[3001][3001];
int pre[3001][3001];

int calc(int ac,int bc){
	return pre[ac][bc]-pre[ac][bc-bb]-pre[ac-aa][bc]+pre[ac-aa][bc-bb];
}
int check(int mid){
	for(int i=1;i<n+1;i++){
		for(int j=1;j<m+1;j++){
			if(it[i-1][j-1]<mid){
				pre[i][j]=-1;
			}
			else if(it[i-1][j-1]==mid){
				pre[i][j]=0;
			}
			else{
				pre[i][j]=1;
			}
		}
	}
	for(int i=1;i<n+1;i++){
		for(int j=1;j<m+1;j++){
			pre[i][j]=pre[i-1][j]+pre[i][j]+pre[i][j-1]-pre[i-1][j-1];
		}
	}
	int ma=1;
	for(int i=aa;i<n+1;i++){
		for(int j=bb;j<m+1;j++){
			
			ma=min(ma,calc(i,j));
		}
	}
	return ma;

}
int rectangle(int nn,int  mm,int aaa,int bbb,int tt[3001][3001]){
	n=nn;
	m=mm;
	aa=aaa;
	bb=bbb;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			it[i][j]=tt[i][j];
		}
	}

	int low=1;
	int high=n*m;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)<=0){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ans=high;
	if(check(low)<=0){
		ans=min(ans,low);
	}
	return ans;
//	cout<<ans<<endl;
	
}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>aa>>bb;
	

	return 0;
}*/

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