Submission #421250

#	Time	Username	Problem	Language	Result	Execution time	Memory
421250		rqi	Quality Of Living (IOI10_quality)	C++14	100 / 100	3106 ms	89676 KiB

quality

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

const int mx = 3005;
int csum[mx][mx];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

	for(int i = R; i >= 1; i--){
		for(int j = C; j >= 1; j--){
			Q[i][j] = Q[i-1][j-1];
		}
	}
	int lo = 1;
	int hi = R*C;

	while(lo < hi){
		int mid = (lo+hi)/2;
		for(int i = 1; i <= R; i++){
			for(int j = 1; j <= C; j++){
				if(Q[i][j] < mid){
					csum[i][j] = -1;
				}
				else if(Q[i][j] > mid){
					csum[i][j] = 1;
				}
				else{
					csum[i][j] = 0;
				}
			}
		}

		// cout << "mid: " << mid << "\n";
		// for(int i = 1; i <= R; i++){
		// 	for(int j = 1; j <= C; j++){
		// 		cout << csum[i][j] << " ";
		// 	}
		// 	cout << "\n";
		// }

		for(int i = 1; i <= R; i++){
			for(int j = 1; j <= C; j++){
				csum[i][j]+=csum[i-1][j]+csum[i][j-1]-csum[i-1][j-1];
			}
		}

		// cout << "mid: " << mid << "\n";
		// for(int i = 1; i <= R; i++){
		// 	for(int j = 1; j <= C; j++){
		// 		cout << csum[i][j] << " ";
		// 	}
		// 	cout << "\n";
		// }

		bool works = 0;

		for(int i = H; i <= R; i++){
			for(int j = W; j <= C; j++){
				if(csum[i][j]-csum[i-H][j]-csum[i][j-W]+csum[i-H][j-W] <= 0){
					//cout << mid << " " << i << " " << j << "\n";
					works = 1;
					break;
				}
			}
		}

		if(works){
			hi = mid;
		}
		else{
			lo = mid+1;
		}

	}


	
	return lo;
}

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