oj.uz

Submission #952269

# Submission time Handle Problem Language Result Execution time Memory
952269 2024-03-23T13:00:34 Z Doncho_Bonboncho Quality Of Living (IOI10_quality) C++14
0 / 100
 1 ms 2396 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 <= r ; i++ ){
		for( int j=1 ; j <= w ; 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -