oj.uz

Submission #837899

# Submission time Handle Problem Language Result Execution time Memory
837899 2023-08-25T19:45:56 Z thimote75 Quality Of Living (IOI10_quality) C++14
100 / 100
 1497 ms 175488 KB 
#include "quality.h"

#include <bits/stdc++.h>
using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

igrid VC;

bool check (int R, int C, int H, int W, igrid &V, int M) {
	int count = (H * W + 1) >> 1;

	for (int i = 0; i <= R; i ++)
		VC[i][0] = 0;
	for (int i = 0; i <= C; i ++)
		VC[0][i] = 0;

	for (int i = 1; i <= R; i ++) {
		for (int j = 1; j <= C; j ++) {
			VC[i][j] = VC[i - 1][j]
			         + VC[i][j - 1]
					 - VC[i - 1][j - 1]
					 + (V[i - 1][j - 1] <= M ? 1 : 0);
		}
	}

	for (int i = 0; i + H <= R; i ++) {
		for (int j = 0; j + W <= C; j ++) {
			int lc = VC[i][j] + VC[i + H][j + W]
			      - (VC[i + H][j] + VC[i][j + W]);
			
			if (lc >= count) return true;
		}
	}

	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	VC.resize(R + 1, idata(C + 1));
	igrid V(R, idata(C));
	for (int i = 0; i < R; i ++)
		for (int j = 0; j < C; j ++)
			V[i][j] = Q[i][j];
	
	int a = 0;
	int b = R * C;

	while (b - a > 1) {
		int c = (a + b) >> 1;

		if (check(R, C, H, W, V, c)) b = c;
		else a = c;
	}

	return b;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 852 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 13 ms 3008 KB Output is correct
8 Correct 15 ms 3008 KB Output is correct
9 Correct 11 ms 2900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 13 ms 3008 KB Output is correct
8 Correct 15 ms 3008 KB Output is correct
9 Correct 11 ms 2900 KB Output is correct
10 Correct 153 ms 22852 KB Output is correct
11 Correct 148 ms 22844 KB Output is correct
12 Correct 75 ms 13516 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 13 ms 3008 KB Output is correct
8 Correct 15 ms 3008 KB Output is correct
9 Correct 11 ms 2900 KB Output is correct
10 Correct 153 ms 22852 KB Output is correct
11 Correct 148 ms 22844 KB Output is correct
12 Correct 75 ms 13516 KB Output is correct
13 Correct 1497 ms 175444 KB Output is correct
14 Correct 1425 ms 175488 KB Output is correct
15 Correct 1325 ms 161252 KB Output is correct