제출 #96982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96982		diamond_duke	Cultivation (JOI17_cultivation)	C++11	100 / 100	1884 ms	1756 KiB

cultivation

#include <algorithm>
#include <cstdio>
using ll = long long;
struct point { ll x, y; } arr[305];
struct queue
{
	int que[605], val[605], he = 0, ta = -1;
	ll *arr;
	queue(ll *_arr) : arr(_arr) {}
	inline void push(int x, int y)
	{
		while (he <= ta && arr[y] >= arr[val[ta]])
			ta--;
		que[++ta] = x;
		val[ta] = y;
	}
	inline void pop(int pos)
	{
		while (he <= ta && que[he] < pos)
			he++;
	}
	inline ll front() const { return arr[val[he]]; }
};
std::pair<ll, int> val[605];
int lp[305], rp[305], idx[305];
ll ava[200005], A[605], B[605], C[605];
bool vis[605][305];
int main()
{
	// freopen("JOISC2017-D1T1.in", "r", stdin);
	int H, W, n, cnt = 0;
	scanf("%d%d%d", &H, &W, &n);
	for (int i = 0; i < n; i++)
		scanf("%lld%lld", &arr[i].x, &arr[i].y);
	std::sort(arr, arr + n, [&] (point a, point b) { return a.x < b.x; });
	ava[cnt++] = arr[0].x - 1 + H - arr[n - 1].x;
	for (int i = 1; i < n; i++)
		ava[0] = std::max(ava[0], arr[i].x - arr[i - 1].x - 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			if (i > j && arr[i].x - arr[j].x - 1 > ava[0])
				ava[cnt++] = arr[i].x - arr[j].x - 1;
			if (arr[i].x - 1 + H - arr[j].x > ava[0])
				ava[cnt++] = arr[i].x - 1 + H - arr[j].x;
		}
	}
	std::sort(ava, ava + cnt);
	cnt = std::unique(ava, ava + cnt) - ava;
	for (int i = 0; i < n; i++)
		idx[i] = i;
	std::sort(idx, idx + n, [&] (int x, int y) { return arr[x].y < arr[y].y; });
	ll ans = 1e18;
	for (int t = 0; t < cnt; t++)
	{
		auto add = [&] (int x, int y)
		{
			vis[x][y] = true;
			int lst = -1;
			A[x] = B[x] = C[x] = 0;
			for (int i = 0; i < n; i++)
			{
				if (!vis[x][idx[i]])
					continue;
				if (-1 == lst)
					A[x] = arr[idx[i]].y - 1;
				else
					B[x] = std::max(B[x], arr[idx[i]].y - lst - 1);
				lst = arr[idx[i]].y;
			}
			C[x] = W - lst;
		};
		for (int i = 0; i < n; i++)
		{
			while (lp[i] < n && arr[i].x + ava[t] >= arr[lp[i]].x)
			{
				if (arr[i].x <= arr[lp[i]].x)
					add(lp[i], i);
				lp[i]++;
			}
			while (rp[i] < n && arr[i].x + ava[t] + 1 >= arr[rp[i]].x)
			{
				if (arr[i].x < arr[rp[i]].x)
					add(i + n, rp[i]);
				rp[i]++;
			}
			val[i] = {arr[i].x, i};
			val[i + n] = {arr[i].x + ava[t] + 1, i + n};
		}
		std::merge(val, val + n, val + n, val + n * 2, val);
		queue que[] = {A, B, C};
		for (int i = 0, j = 0; i < n * 2 && val[i].first + H <= val[n * 2 - 1].first; i++)
		{
			for (auto &Q : que)
				Q.pop(i);
			while (j < n * 2 && val[i].first + H > val[j].first)
			{
				for (auto &Q : que)
					Q.push(j, val[j].second);
				j++;
			}
			ans = std::min(ans, std::max(que[0].front() + que[2].front(), que[1].front()) + ava[t]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

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

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