Submission #309975

#	Time	Username	Problem	Language	Result	Execution time	Memory
309975		sofapuden	Quality Of Living (IOI10_quality)	C++14	100 / 100	4364 ms	140520 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 l = 0, r = R*C;
	int good;
	while(l < r){
		int mid = (l+r+1)/2;
		vector<vector<int>> gri(R,vector<int>(C));
		for(int i = 0; i < R; ++i){
			for(int j = 0; j <  C; ++j){
				if(Q[i][j] < mid) gri[i][j] = -1;
				if(Q[i][j] > mid) gri[i][j] = 1;
				if(Q[i][j] == mid) gri[i][j] = 0;
				if(i)gri[i][j]+=gri[i-1][j];
				if(j)gri[i][j]+=gri[i][j-1];
				if(i && j)gri[i][j]-=gri[i-1][j-1];
			}
		}
		int best = INT_MAX;
		for(int i = H-1; i < R; ++i){
			for(int j = W-1; j < C; ++j){
				int now = gri[i][j];
				if(i >= H)now-=gri[i-H][j];
				if(j >= W)now-=gri[i][j-W];
				if(i >= H && j >= W)now+=gri[i-H][j-W];
				best = min(best,now);
			}
		}
		if(best <= 0){r = mid-1;good = mid;}
		else l = mid;
	}
	return good;
	
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:35:9: warning: 'good' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |  return good;
      |         ^~~~

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