oj.uz

Submission #271459

# Submission time Handle Problem Language Result Execution time Memory
271459 2020-08-18T06:17:06 Z shrek12357 Quality Of Living (IOI10_quality) C++14
100 / 100
 2445 ms 175656 KB 
#include <iostream>
#include <vector>
#include "quality.h"
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <unordered_set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;

#define MAXN 3005
int r, c, h, w;
int grid[MAXN][MAXN];

bool check(int mid) {
	int pre[MAXN][MAXN];
	int xCoord = -1, yCoord = 1;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int temp = -1;
			if (grid[i][j] <= mid) {
				temp = 1;
			}
			pre[i][j] = temp;
			if (i > 0) {
				pre[i][j] += pre[i - 1][j];
			}
			if (j > 0) {
				pre[i][j] += pre[i][j - 1];
			}
			if (i > 0 && j > 0) {
				pre[i][j] -= pre[i - 1][j - 1];
			}
			if (i - h + 1 >= 0 && j - w + 1 >= 0) {
				int cur = pre[i][j];
				if (i - h >= 0) {
					cur -= pre[i - h][j];
				}
				if (j - w >= 0) {
					cur -= pre[i][j - w];
				}
				if (i - h >= 0 && j - w >= 0) {
					cur += pre[i - h][j - w];
				}
				if (cur >= 0) {
					return true;
				}
			}
		}
	}
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r = R; c = C; h = H; w = W;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			grid[i][j] = Q[i][j];
		}
	}
	int lo = 1;
	int hi = r * c;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
	}
	return lo;
}

Compilation message

quality.cpp: In function 'bool check(int)':
quality.cpp:21:6: warning: unused variable 'xCoord' [-Wunused-variable]
   21 |  int xCoord = -1, yCoord = 1;
      |      ^~~~~~
quality.cpp:21:19: warning: unused variable 'yCoord' [-Wunused-variable]
   21 |  int xCoord = -1, yCoord = 1;
      |                   ^~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 672 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1696 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 672 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1696 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 22 ms 5504 KB Output is correct
8 Correct 23 ms 5504 KB Output is correct
9 Correct 20 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 672 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1696 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 22 ms 5504 KB Output is correct
8 Correct 23 ms 5504 KB Output is correct
9 Correct 20 ms 5376 KB Output is correct
10 Correct 256 ms 30900 KB Output is correct
11 Correct 253 ms 30944 KB Output is correct
12 Correct 138 ms 21496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 672 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1696 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 22 ms 5504 KB Output is correct
8 Correct 23 ms 5504 KB Output is correct
9 Correct 20 ms 5376 KB Output is correct
10 Correct 256 ms 30900 KB Output is correct
11 Correct 253 ms 30944 KB Output is correct
12 Correct 138 ms 21496 KB Output is correct
13 Correct 2445 ms 175588 KB Output is correct
14 Correct 2383 ms 175656 KB Output is correct
15 Correct 2283 ms 168464 KB Output is correct