Submission #296926

#	Time	Username	Problem	Language	Result	Execution time	Memory
296926		Bill_00	Quality Of Living (IOI10_quality)	C++14	100 / 100	2507 ms	122872 KiB

quality

#include <quality.h>
#include <bits/stdc++.h>
using namespace std;
int a[3001][3001],x,y,X,Y,dp[3001][3001];
bool check(int k){
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			if(a[i][j]<=k){
				dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+1;
			}
			else dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			if(i>=X && j>=Y){
				int o=dp[i][j]-dp[i][j-Y]-dp[i-X][j]+dp[i-X][j-Y];
				//cout << o << ' ' << i <<  ' ' << j << ' ' << k << endl;
				if(o>(X*Y/2)) return 0;
			}
		}
	}
	return 1;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
	x=R;
	y=C;
	X=H;
	Y=W;
	for(int i=0;i<R;i++){
		for(int j=0;j<C;j++){
			a[i+1][j+1]=Q[i][j];
		}
	}
	int l=1,r=R*C;
	while(l<r){
		int mid=l+r>>1;
		check(mid)?l=mid+1:r=mid;
		//cout << l << ' ' << r << endl;
	}
	check(l)?l=l+1:l=l;
	return l;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=l+r>>1;
      |           ~^~

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