oj.uz

답안 #271323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271323 2020-08-18T05:40:44 Z shrek12357 삶의 질 (IOI10_quality) C++14
0 / 100
 1 ms 640 KB 
#include <iostream>
#include "quality.h"
#include <vector>
#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++) {
			if (grid[i][j] == mid) {
				xCoord = i;
				yCoord = j;
			}
			int temp = 0;
			if (grid[i][j] < mid) {
				temp++;
			}
			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];
			}
		}
	}
	for (int i = xCoord; i < xCoord + h; i++) {
		for (int j = yCoord; j < yCoord + w; j++) {
			if (i - h + 1 < 0 || i >= r || j - w + 1 < 0 || j >= c) {
				continue;
			}
			int temp = pre[i][j];
			if (i - h >= 0) {
				temp -= pre[i - h][j];
			}
			if (j - w >= 0) {
				temp -= pre[i][j - w];
			}
			if (i - h >= 0 && j - w >= 0) {
				temp += pre[i - h][j - w];
			}
			if (temp == (h*w) / 2) {
				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;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -