제출 #60245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60245		ainta	Cultivation (JOI17_cultivation)	C++17	60 / 100	2068 ms	14364 KiB

cultivation

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
long long W, H, n, S[610][610], M[610][610], U[610][610];
set<long long>SX, SY;
long long YY[1000000];
struct point {
	long long x, y;
}w[330];
struct Rect {
	long long x1, y1, x2, y2;
}R[330];
long long X[610], Y[610];
bool Pos(long long dx, long long dy) {
	long long i, j;
	long long CX = 0, CY = 0;
	for (i = 1; i <= n; i++) {
		X[CX++] = w[i].x;
		X[CX++] = w[i].x + dx + 1;
		Y[CY++] = w[i].y;
		Y[CY++] = w[i].y + dy + 1;
	}
	sort(X, X + CX);
	sort(Y, Y + CY);
	CX = unique(X, X + CX) - X;
	CY = unique(Y, Y + CY) - Y;
	for (i = 0; i <= CX; i++)for (j = 0; j <= CY; j++)S[i][j] = 0;
	for (i = 1; i <= n; i++) {
		R[i].x1 = lower_bound(X, X + CX, w[i].x) - X;
		R[i].x2 = lower_bound(X, X + CX, w[i].x + dx + 1) - X;
		R[i].y1 = lower_bound(Y, Y + CY, w[i].y) - Y;
		R[i].y2 = lower_bound(Y, Y + CY, w[i].y + dy + 1) - Y;
		S[R[i].x1][R[i].y1]++;
		S[R[i].x1][R[i].y2]--;
		S[R[i].x2][R[i].y1]--;
		S[R[i].x2][R[i].y2]++;
	}
	for (i = 0; i < CX; i++)for (j = 1; j < CY; j++)S[i][j] += S[i][j - 1];
	for (i = 1; i < CX; i++)for (j = 0; j < CY; j++)S[i][j] += S[i -1][j];
	for (i = 0; i < CX - 1; i++) {
		for (j = 0; j < CY - 1; j++) {
			if (!S[i][j])M[i][j] = 0;
			else if (j == 0)M[i][j] = Y[j + 1] - Y[j];
			else M[i][j] = Y[j + 1] - Y[j] + M[i][j - 1];
			if (M[i][j] >= H) {
				if (i == 0)U[i][j] = X[i + 1] - X[i];
				else U[i][j] = U[i - 1][j] + X[i + 1] - X[i];
				if (U[i][j] >= W)return true;
			}
			else {
				U[i][j] = 0;
			}
		}
	}
	return false;
}
int main() {
	//freopen("input.txt", "r", stdin);
	long long i, j, CY = 0;
	scanf("%lld%lld%lld", &W, &H, &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld%lld", &w[i].x, &w[i].y);
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (w[i].x <= w[j].x) {
				if(w[j].x>w[i].x)SX.insert(w[j].x - w[i].x - 1);
			}
			SX.insert(w[i].x - 1 + W - w[j].x);
			SX.insert(w[j].x - w[i].x + W);
			if (w[i].y <= w[j].y) {
				if (w[j].y>w[i].y)SY.insert(w[j].y - w[i].y - 1);
			}
			SY.insert(w[i].y - 1 + H - w[j].y);
			SY.insert(w[j].y - w[i].y + H);
		}
	}
	long long res = 4e9;
	for (auto &y : SY) {
		YY[CY++] = y;
	}
	for (auto &x : SX) {
		long long b = 0, e = CY - 1, r = CY;
		while (b <= e) {
			long long mid = (b + e) >> 1;
			if (Pos(x, YY[mid])) {
				r = mid;
				e = mid - 1;
			}
			else b = mid + 1;
		}
		if (r != CY) {
			res = min(res, x + YY[r]);
		}
	}
	printf("%lld\n", res);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'int main()':
cultivation.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &W, &H, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &w[i].x, &w[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20