Submission #519145

#	Time	Username	Problem	Language	Result	Execution time	Memory
519145		lovrot	Quality Of Living (IOI10_quality)	C++14	100 / 100	2305 ms	210564 KiB

quality

#include <bits/stdc++.h> 

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define siz size()
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const ll INF = 1e18;                              
const int LOG = 20;
const int OFF = (1 << LOG);
const int N = 3001;
const int M = 3001; 

int n, m, a, b, mat[N][M];
ll suf[N][M];

int rectangle(int R, int C, int H, int W, int Q[N][M]){ 
	n = R;
	m = C;
	a = H;
	b = W;
	pri(i, 0, N, 1) 
		pri(j, 0, M, 1)
			mat[i][j] = Q[i][j];
		
	int lo = 0;
	int hi = n * m;

	while(lo < hi){
		int mi = (lo + hi + 1) / 2;

		//cout << lo << " " << mi << " " << hi << " : ";

		ll mn = INF;

		pri(i, 1, n + 1, 1){
			pri(j, 1, m + 1, 1){ 	
				int val = 0;
				if(mat[i - 1][j - 1] < mi) val = -1;
				if(mat[i - 1][j - 1] > mi) val = 1; 

				suf[i][j] = suf[i - 1][j] + suf[i][j - 1] - suf[i - 1][j - 1] + val;
				
				if(i >= a && j >= b)
					mn = min(mn, suf[i][j] - suf[i - a][j] - suf[i][j - b] + suf[i - a][j - b]);
			}
		}	

		//cout << mn << "\n";

		if(mn >= 0)	
			lo = mi;
		else
			hi = mi - 1;
	}

	return lo;
}

/*
int main(){
	ios_base::sync_with_stdio(false);  
	cin.tie(0);
	cout.tie(0);
	setprecision(9);

	int R=5, C=5, H=3, W=3;
	int Q[N][M] = {{5, 11, 12, 16, 25}, 
				 {17, 18, 2, 7, 10},
				 {4, 23, 20, 3, 1},
				 {24, 21, 19, 14, 9},
				 {6, 22, 8, 13, 15}};

	cout << rectangle(R, C, H, W, Q) << "\n"; 
	return 0;
} */

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