Submission #1112783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112783		nikolashami	Quality Of Living (IOI10_quality)	C++17	100 / 100	1116 ms	175624 KiB

quality

#include <bits/stdc++.h>
using namespace std;

#include "quality.h"

const int N=3004;
int n,m,h,w,x,a[N][N],pr[N][N];

int cmp(int br){
	return (br==x?0:br>x?-1:1);
}

bool chk(){
	pr[0][0]=cmp(a[0][0]);

	for(int i=1;i<n;++i)
	    pr[i][0]=pr[i-1][0]+cmp(a[i][0]);
	
	for(int i=1;i<m;++i)
	    pr[0][i]=pr[0][i-1]+cmp(a[0][i]);

	for (int i=1;i<n;++i) {
	    for (int j=1;j<m;++j)
	        pr[i][j]=pr[i-1][j]+pr[i][j-1]
	                    -pr[i-1][j-1]+cmp(a[i][j]);
	}

	for(int i=0;i+h<n;++i){
		for(int j=0;j+w<m;++j){
			int lg=(!i||!j?0:pr[i-1][j-1]);
			int dg=(!i?0:pr[i-1][j+w]);
			int dl=(!j?0:pr[i+h][j-1]);
			int dd=(pr[i+h][j+w]);
			int s=(dd-dl-dg+lg);
			if(s>=0)
				return 1;
		}
	}

	return 0;
}

int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
	n=R,m=C,h=H-1,w=W-1;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			a[i][j]=Q[i][j];
	int l=1,r=n*m,ans=r;
	while(l<=r){
		x=(l+r)/2;
		if(chk()){
			ans=x;
			r=x-1;
		}else
			l=x+1;
	}
	return ans;
}

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