Submission #286942

#	Time	Username	Problem	Language	Result	Execution time	Memory
286942		mraron	Quality Of Living (IOI10_quality)	C++14	100 / 100	4486 ms	140480 KiB

quality

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

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int can=R*C;
	vector<vector<int>> t(R, vector<int>(C));

	for(int i=25;i>=0;i--) {
		int akt=can-(1<<i);
		if(akt>=1) {
			for(int i=0;i<R;++i) {
				for(int j=0;j<C;++j) {
					if(akt==Q[i][j]) t[i][j]=0;
					else if(akt<Q[i][j]) t[i][j]=1;
					else if(akt>Q[i][j]) t[i][j]=-1;
				}
			}
			
			for(int i=0;i<R;++i) {
				for(int j=0;j<C;++j) {
					if(i) t[i][j]+=t[i-1][j];
					if(j) t[i][j]+=t[i][j-1];
					if(i&&j) t[i][j]-=t[i-1][j-1];
				}
			}
			
			bool ok=false;
			for(int i=0;!ok&&i+H-1<R;++i) {
				for(int j=0;!ok&&j+W-1<C;++j) {
					int sum=t[i+H-1][j+W-1];
					if(i) sum-=t[i-1][j+W-1];
					if(j) sum-=t[i+H-1][j-1];
					if(i&&j) sum+=t[i-1][j-1];
					if(sum<=0) ok=true;
				}
			}
			
			if(ok) can=akt;
		}
	}
	
	return can;
	
}

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