Submission #516641

#	Time	Username	Problem	Language	Result	Execution time	Memory
516641		CaroLinda	Quality Of Living (IOI10_quality)	C++14	100 / 100	2191 ms	175596 KiB

quality

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

const int MAX = 3010 ;

using namespace std ;

int N , M , R ,C ;
int grid[MAX][MAX] ;
int sv[MAX][MAX] ;

int getSum(int a, int b, int c, int d) { return sv[c][d]-sv[c][b-1]-sv[a-1][d]+sv[a-1][b-1] ; } 

bool test(int x){
	for(int i = 1 ; i <= R ; i++ )
		for(int j = 1 ; j <= C ; j++ ){
			sv[i][j]=sv[i-1][j]+sv[i][j-1]-sv[i-1][j-1] ;
			if( grid[i][j] < x ) sv[i][j]-- ;
			if(grid[i][j] > x ) sv[i][j]++ ;
		}

	for(int i = 1 ; i+N-1 <= R ; i++ )
		for(int j = 1 ; j+M-1 <= C ; j++ )
			if( getSum(i,j,i+N-1, j+M-1) <= 0 ) return true ;

	return false ;
}

int rectangle(int _R, int _C, int H, int W, int Q[3001][3001]) {
	
	N = H , M = W ;
	R = _R , C = _C ;

	for(int i = 1 ; i <= R ; i++ )
		for(int j = 1 ; j<= C ; j++ ) grid[i][j]=Q[i-1][j-1] ;

  	int l = 0 , r = R*C-1 , mid , best ;
  	while(l <= r ){
  		mid=(l+r)>>1 ;
  		if(test(mid) ) {
  			best=mid;
  			r=mid-1 ;
  		}
  		else l=mid+1 ;
  	}
  	return best ;
}

Compilation message (stderr)

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

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