Submission #976583

#	Time	Username	Problem	Language	Result	Execution time	Memory
976583		LaviniaTornaghi	Quality Of Living (IOI10_quality)	C++14	100 / 100	2572 ms	176120 KiB

quality

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

int prf(vector<vector<int>> &ps, int x1, int y1, int x2, int y2){
	return ps[x2][y2]-ps[x2][y1]-ps[x1][y2]+ps[x1][y1];
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> q(R,vector<int>(C));
	int l = 0, r= R*C;

	auto check = [&](int m)->bool {
		for(int i=0;i<R;i++){
			for(int j= 0;j<C;j++){
				if(Q[i][j]>m) q[i][j]=-1;
				else if(Q[i][j]==0) q[i][j]=0;
				else q[i][j]=1;
			}
		}
		vector<vector<int>> ps(R+2,vector<int>(C+2));
		for(int i=1;i<=R;i++){
			for(int j=1;j<=C;j++){
				ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + q[i-1][j-1];
			}
		}
		bool ispossible=0;
		for(int i=0;i<=R-H;i++){
			for(int j=0;j<=C-W;j++){
				if(prf(ps,i,j,i+H,j+W)>=0) ispossible=1;
			}
		}
		return ispossible;
	};

	while(r-l>1){
		int m = (l+r)/2;
		if(check(m))r =m;
		else l = m;
	}
	return r;
}

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