oj.uz

Submission #727950

# Submission time Handle Problem Language Result Execution time Memory
727950 2023-04-21T16:28:33 Z rainboy OBELISK (NOI14_obelisk) C
25 / 25
 30 ms 852 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 468 KB Output is correct
2 Correct 19 ms 468 KB Output is correct
3 Correct 18 ms 432 KB Output is correct
4 Correct 18 ms 472 KB Output is correct
5 Correct 20 ms 400 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 852 KB Output is correct
2 Correct 24 ms 644 KB Output is correct
3 Correct 24 ms 652 KB Output is correct
4 Correct 27 ms 816 KB Output is correct
5 Correct 30 ms 676 KB Output is correct