oj.uz

Submission #519145

# Submission time Handle Problem Language Result Execution time Memory
519145 2022-01-25T18:18:14 Z lovrot Quality Of Living (IOI10_quality) C++14
100 / 100
 2305 ms 210564 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35780 KB Output is correct
2 Correct 24 ms 35784 KB Output is correct
3 Correct 23 ms 35828 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35780 KB Output is correct
2 Correct 24 ms 35784 KB Output is correct
3 Correct 23 ms 35828 KB Output is correct
4 Correct 36 ms 36472 KB Output is correct
5 Correct 38 ms 36448 KB Output is correct
6 Correct 34 ms 36560 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35780 KB Output is correct
2 Correct 24 ms 35784 KB Output is correct
3 Correct 23 ms 35828 KB Output is correct
4 Correct 36 ms 36472 KB Output is correct
5 Correct 38 ms 36448 KB Output is correct
6 Correct 34 ms 36560 KB Output is correct
7 Correct 41 ms 39536 KB Output is correct
8 Correct 42 ms 39480 KB Output is correct
9 Correct 39 ms 39344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35780 KB Output is correct
2 Correct 24 ms 35784 KB Output is correct
3 Correct 23 ms 35828 KB Output is correct
4 Correct 36 ms 36472 KB Output is correct
5 Correct 38 ms 36448 KB Output is correct
6 Correct 34 ms 36560 KB Output is correct
7 Correct 41 ms 39536 KB Output is correct
8 Correct 42 ms 39480 KB Output is correct
9 Correct 39 ms 39344 KB Output is correct
10 Correct 272 ms 62212 KB Output is correct
11 Correct 247 ms 62044 KB Output is correct
12 Correct 150 ms 52784 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35780 KB Output is correct
2 Correct 24 ms 35784 KB Output is correct
3 Correct 23 ms 35828 KB Output is correct
4 Correct 36 ms 36472 KB Output is correct
5 Correct 38 ms 36448 KB Output is correct
6 Correct 34 ms 36560 KB Output is correct
7 Correct 41 ms 39536 KB Output is correct
8 Correct 42 ms 39480 KB Output is correct
9 Correct 39 ms 39344 KB Output is correct
10 Correct 272 ms 62212 KB Output is correct
11 Correct 247 ms 62044 KB Output is correct
12 Correct 150 ms 52784 KB Output is correct
13 Correct 2305 ms 210564 KB Output is correct
14 Correct 2104 ms 210516 KB Output is correct
15 Correct 1978 ms 203468 KB Output is correct