oj.uz

Submission #952270

# Submission time Handle Problem Language Result Execution time Memory
952270 2024-03-23T13:05:58 Z Doncho_Bonboncho Quality Of Living (IOI10_quality) C++14
100 / 100
 1262 ms 140076 KB 
#include <bits/stdc++.h>
#include "quality.h"
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
using namespace std;


template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
 
#ifndef LOCAL
#define cerr if(false) cerr
#define endl "\n"
#endif

#define out(x) #x << "=" << x << " "

const int MAX_N = 3001;

int pref[MAX_N][MAX_N];
int r, c, h, w;

bool f( int x ){

	for( int i=1 ; i + h-1 <= r ; i++ ){
		for( int j=1 ; j + w-1 <= c ; j++ ){
			int x1 = i, y1 = j;
			int x2 = i + h-1, y2 = j + w-1;

			cerr << out( x1 ) << out( y1 ) << out( x2 ) << out( y2 ) << endl;
			int currLess = pref[x2][y2] - pref[x2][y1-1] - pref[x1-1][y2] + pref[x1-1][y1-1];
			cerr << out( pref[x2][y2] ) << out( pref[x2][y1-1] ) << out( pref[x1-1][y2] ) << out( pref[x1-1][y1-1] ) << endl;
			cerr << out( currLess ) << endl;

			if( currLess > ( w * h ) /2 ) return true;
		}
	}
	cerr << " nqma " <<endl;
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r = R; c = C; h = H; w = W;

	int l = 0, r = R * C +1;
	while( l != r-1 ){
		int m = ( l + r ) >> 1;
		cerr << out( l ) << out( m ) << out( r ) << endl;

		for( int i=1 ; i <= R ; i++ ){
			for( int j=1 ; j <= C ; j++ ){
				//cerr << out( i ) << out( j ) << endl;
				pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + bool( Q[i-1][j-1] <= m );
				//cerr << out( pref[i-1][j] ) << out( pref[i][j-1] ) << out( pref[i-1][j-1] ) << out( Q[i-1][j-1] ) << out( m )  << endl << out( pref[i][j] ) << endl;
			}
		}

		for( int i=1 ; i <= R ; i++ ){
			for( int j=1 ; j <= C ; j++ ){
				cerr << pref[i][j] << " ";
			}
			cerr << endl;
		}
		cerr << endl;
		if( f( m ) ) r = m;
		else l = m;
	}

	return l +1;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 5980 KB Output is correct
8 Correct 10 ms 6492 KB Output is correct
9 Correct 9 ms 6492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 5980 KB Output is correct
8 Correct 10 ms 6492 KB Output is correct
9 Correct 9 ms 6492 KB Output is correct
10 Correct 102 ms 28716 KB Output is correct
11 Correct 97 ms 28496 KB Output is correct
12 Correct 57 ms 22832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 5980 KB Output is correct
8 Correct 10 ms 6492 KB Output is correct
9 Correct 9 ms 6492 KB Output is correct
10 Correct 102 ms 28716 KB Output is correct
11 Correct 97 ms 28496 KB Output is correct
12 Correct 57 ms 22832 KB Output is correct
13 Correct 1262 ms 140056 KB Output is correct
14 Correct 916 ms 140076 KB Output is correct
15 Correct 883 ms 133204 KB Output is correct