Submission #727950

#	Time	Username	Problem	Language	Result	Execution time	Memory
727950		rainboy	OBELISK (NOI14_obelisk)	C11	25 / 25	30 ms	852 KiB

obelisk

#include <stdio.h>
#include <string.h>

#define N	100
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long abs_(long long a) { return a > 0 ? a : -a; }

long long dist(long long x, long long y, long long l) {
	int u, v;
	long long ans;

	if (l == 1)
		return x + y;
	ans = INF;
	for (u = 0; u < 2; u++)
		if (u || x % (l + 1) == 0)
			for (v = 0; v < 2; v++)
				if (v || y % (l + 1) == 0) {
					long long dx = min(max(x / (l + 1), v) * 2 + x % (l + 1), max(x / (l + 1) + 1, v) * 2 + l + 1 - x % (l + 1));
					long long dy = min(max(y / (l + 1), u) * 2 + y % (l + 1), max(y / (l + 1) + 1, u) * 2 + l + 1 - y % (l + 1));

					ans = min(ans, dx + dy);
				}
	return ans;
}

int main() {
	static int xx[N], yy[N], xx_[N], yy_[N];
	static long long dp[N], dp_[N];
	int m, n, n_, l, i, j, x1, y1, x2, y2;
	long long ans;

	scanf("%d%d%d%d%d%d", &m, &l, &x1, &y1, &x2, &y2);
	n = 0;
	xx[n] = x1, yy[n] = y1, dp[n] = 0, n++;
	while (m--) {
		scanf("%d", &n_);
		for (j = 0; j < n_; j++) {
			scanf("%d%d", &xx_[j], &yy_[j]);
			dp_[j] = INF;
			for (i = 0; i < n; i++)
				dp_[j] = min(dp_[j], dp[i] + dist(abs_(xx_[j] - xx[i]), abs_(yy_[j] - yy[i]), l));
		}
		memcpy(xx, xx_, n_ * sizeof *xx_);
		memcpy(yy, yy_, n_ * sizeof *yy_);
		memcpy(dp, dp_, n_ * sizeof *dp_);
		n = n_;
	}
	ans = INF;
	for (i = 0; i < n; i++)
		ans = min(ans, dp[i] + dist(abs_(x2 - xx[i]), abs_(y2 - yy[i]), l));
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

obelisk.c: In function 'main':
obelisk.c:36:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d%d%d%d%d%d", &m, &l, &x1, &y1, &x2, &y2);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
obelisk.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &n_);
      |   ^~~~~~~~~~~~~~~~
obelisk.c:42:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |    scanf("%d%d", &xx_[j], &yy_[j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 7 / 7