oj.uz

Submission #516641

# Submission time Handle Problem Language Result Execution time Memory
516641 2022-01-21T17:23:03 Z CaroLinda Quality Of Living (IOI10_quality) C++14
100 / 100
 2191 ms 175596 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1592 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1592 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5444 KB Output is correct
8 Correct 17 ms 5456 KB Output is correct
9 Correct 17 ms 5256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1592 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5444 KB Output is correct
8 Correct 17 ms 5456 KB Output is correct
9 Correct 17 ms 5256 KB Output is correct
10 Correct 234 ms 30820 KB Output is correct
11 Correct 264 ms 30820 KB Output is correct
12 Correct 112 ms 21448 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 664 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1592 KB Output is correct
6 Correct 2 ms 1612 KB Output is correct
7 Correct 18 ms 5444 KB Output is correct
8 Correct 17 ms 5456 KB Output is correct
9 Correct 17 ms 5256 KB Output is correct
10 Correct 234 ms 30820 KB Output is correct
11 Correct 264 ms 30820 KB Output is correct
12 Correct 112 ms 21448 KB Output is correct
13 Correct 2191 ms 175592 KB Output is correct
14 Correct 2139 ms 175596 KB Output is correct
15 Correct 1985 ms 168480 KB Output is correct