oj.uz

Submission #856808

# Submission time Handle Problem Language Result Execution time Memory
856808 2023-10-04T15:47:48 Z drome Quality Of Living (IOI10_quality) C++14
100 / 100
 3830 ms 175468 KB 
#include "quality.h"
#include <string.h>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	ll lo = 1, hi = R * C;

	int leq[3001][3001];
	int ps[3001][3001];


	for (int _=0;_<100;_++) {
		ll mi = (lo + hi) / 2;
		memset(leq, 0, sizeof(leq));
		for (int i=0;i<R;i++) for (int j=0;j<C;j++) {
			leq[i][j] = (Q[i][j] <= mi);
			ps[i][j] = leq[i][j];
			if (i) ps[i][j] += ps[i-1][j];
			if (j) ps[i][j] += ps[i][j-1];
			if (i && j) ps[i][j] -= ps[i-1][j-1];
		}

		// cout << "MI: " << mi << endl;
		// for (int i=0;i<R;i++) {
		// 	for (int j=0;j<C;j++) {
		// 		cout << leq[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }

		// for (int i=0;i<R;i++) {
		// 	for (int j=0;j<C;j++) {
		// 		cout << ps[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }

		ll maxsum = 0;
		for (int i=0;i+H<=R;i++) for (int j=0;j+W<=C;j++) {
			ll sum = ps[i+H-1][j+W-1];
			if (i) sum -= ps[i-1][j+W-1];
			if (j) sum -= ps[i+H-1][j-1];
			if (i && j) sum += ps[i-1][j-1];
			maxsum = max(maxsum, sum);
		}

		// cout << "maxsum: " << maxsum << endl;

		if (maxsum > (W * H) / 2) hi = mi;
		else lo = mi + 1;
	}


	return lo;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 73020 KB Output is correct
2 Correct 294 ms 73020 KB Output is correct
3 Correct 292 ms 73028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 73020 KB Output is correct
2 Correct 294 ms 73020 KB Output is correct
3 Correct 292 ms 73028 KB Output is correct
4 Correct 298 ms 73068 KB Output is correct
5 Correct 301 ms 73076 KB Output is correct
6 Correct 294 ms 73076 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 73020 KB Output is correct
2 Correct 294 ms 73020 KB Output is correct
3 Correct 292 ms 73028 KB Output is correct
4 Correct 298 ms 73068 KB Output is correct
5 Correct 301 ms 73076 KB Output is correct
6 Correct 294 ms 73076 KB Output is correct
7 Correct 329 ms 75492 KB Output is correct
8 Correct 329 ms 75604 KB Output is correct
9 Correct 336 ms 75552 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 73020 KB Output is correct
2 Correct 294 ms 73020 KB Output is correct
3 Correct 292 ms 73028 KB Output is correct
4 Correct 298 ms 73068 KB Output is correct
5 Correct 301 ms 73076 KB Output is correct
6 Correct 294 ms 73076 KB Output is correct
7 Correct 329 ms 75492 KB Output is correct
8 Correct 329 ms 75604 KB Output is correct
9 Correct 336 ms 75552 KB Output is correct
10 Correct 723 ms 90132 KB Output is correct
11 Correct 663 ms 90308 KB Output is correct
12 Correct 518 ms 86612 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 73020 KB Output is correct
2 Correct 294 ms 73020 KB Output is correct
3 Correct 292 ms 73028 KB Output is correct
4 Correct 298 ms 73068 KB Output is correct
5 Correct 301 ms 73076 KB Output is correct
6 Correct 294 ms 73076 KB Output is correct
7 Correct 329 ms 75492 KB Output is correct
8 Correct 329 ms 75604 KB Output is correct
9 Correct 336 ms 75552 KB Output is correct
10 Correct 723 ms 90132 KB Output is correct
11 Correct 663 ms 90308 KB Output is correct
12 Correct 518 ms 86612 KB Output is correct
13 Correct 3830 ms 175380 KB Output is correct
14 Correct 3566 ms 175468 KB Output is correct
15 Correct 3549 ms 168312 KB Output is correct