Submission #1103950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103950		ThylOne	Quality Of Living (IOI10_quality)	C++14	100 / 100	1773 ms	140132 KiB

quality

#include "quality.h"
#include <atomic>
#include<bits/stdc++.h>

using namespace std;
//possibke avec une médiance <=X
bool oracle(int X,int R,int C,int H,int W,int Q[3001][3001]){
	int cumulatif[R+1][C+1];
	for(int i = 0;i<=R;i++)
		for(int j=0;j<=C;j++)
			cumulatif[i][j] = 0;
	int act_sum = 0;
	for(int i = 1;i<=R;i++){
		act_sum=0;
		for(int j = 1;j<=C;j++){
			if(Q[i-1][j-1]<X)act_sum++;
			else if(Q[i-1][j-1]>X)act_sum--;
			cumulatif[i][j] = act_sum+cumulatif[i-1][j];
		}
	}
	
	#define query(y1,x1,y2,x2) \
		(cumulatif[y2][x2] - cumulatif[y2][x1-1] - cumulatif[y1-1][x2] + cumulatif[y1-1][x1-1])
	

	for(int y1 = 1 ; y1 + H -1 <= R; y1++)
		for(int x1 = 1; x1 + W -1<= C; x1++)
			if(query(y1, x1, y1+H-1 , x1+W-1)>=0)
				return true;

	return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int low = R*C;
	int high = 0;
	while(low - high > 1){
		int mid = (low+high)/2;
		if(oracle(mid,R,C,H,W,Q)){
			low = mid;
		}else{
			high = mid;
		}
	}
	return low;
}

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