Submission #271459

#	Time	Username	Problem	Language	Result	Execution time	Memory
271459		shrek12357	Quality Of Living (IOI10_quality)	C++14	100 / 100	2445 ms	175656 KiB

quality

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20