제출 #1245246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245246		AMel0n	삶의 질 (IOI10_quality)	C++20	100 / 100	1120 ms	70896 KiB

quality

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

#include "quality.h"
int ps[3001][3001];
signed char bro(int x, int &R, int &C, int &H, int &W, int Q[3001][3001]) {
	FOR(r, R) FOR(c, C) {
		ps[r][c] = 0;
		if (r > 0) ps[r][c] += ps[r-1][c];
		if (c > 0) ps[r][c] += ps[r][c-1];
		if (r > 0 && c > 0) ps[r][c] -= ps[r-1][c-1];
		ps[r][c] += ((Q[r][c] <= x) ? 1 : -1);
	}

	for(int r = 0; r + H < R; r++) {
		for(int c = 0; c + W < C; c++) {
			int res = ps[r+H][c+W];
			if (r > 0) res -= ps[r-1][c+W];
			if (c > 0) res -= ps[r+H][c-1];
			if (r > 0 && c > 0) res += ps[r-1][c-1];
			if (res >= 0) return 1;
		}
	}
	return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	H--; W--;
	int l = 1, r = R * C + 1;
	while(l < r - 1) {
		int m = (l + r - 1) / 2;
		if (bro(m, R, C, H, W, Q)) r = m + 1;
		else l = m + 1;
	}
	return l;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20