oj.uz

Submission #536331

# Submission time Handle Problem Language Result Execution time Memory
536331 2022-03-12T22:55:44 Z rainboy 도장 모으기 (JOI14_stamps) C
100 / 100
 163 ms 460 KB 
#include <stdio.h>
#include <string.h>

#define N	3000
#define M	((N + 2) * 2)
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int main() {
	static long long dp[M + 1], dq[M + 1];
	int n, m, t, k;

	scanf("%d%d", &n, &t), m = (n + 2) * 2;
	memset(dp, 0x3f, (m + 1) * sizeof *dp), dp[0] = t;
	while (n--) {
		int u, v, d, e;

		scanf("%d%d%d%d", &u, &v, &d, &e);
		memset(dq, 0x3f, (m + 1) * sizeof *dq);
		for (k = 0; k <= m; k++) {
			long long x = dp[k];

			if (x == INF)
				continue;
			dq[k] = min(dq[k], x + u + v);
			if (k > 0) {
				dq[k] = min(dq[k], x + d + e);
				dq[k - 1] = min(dq[k - 1], x + u + e);
			}
			if (k < m)
				dq[k + 1] = min(dq[k + 1], x + d + v);
		}
		for (k = m; k > 0; k--)
			dq[k - 1] = min(dq[k - 1], dq[k] + u + e);
		for (k = 0; k < m; k++)
			dq[k + 1] = min(dq[k + 1], dq[k] + d + v);
		memcpy(dp, dq, (m + 1) * sizeof *dq);
		for (k = 0; k <= m; k++)
			if (dp[k] != INF)
				dp[k] += (long long) t * (k * 2 + 1);
	}
	printf("%lld\n", dp[0]);
	return 0;
}

Compilation message

stamps.c: In function 'main':
stamps.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &t), m = (n + 2) * 2;
      |  ^~~~~~~~~~~~~~~~~~~~~
stamps.c:19:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d%d%d%d", &u, &v, &d, &e);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 428 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 143 ms 416 KB Output is correct
4 Correct 114 ms 416 KB Output is correct
5 Correct 88 ms 416 KB Output is correct
6 Correct 38 ms 340 KB Output is correct
7 Correct 22 ms 356 KB Output is correct
8 Correct 146 ms 432 KB Output is correct
9 Correct 144 ms 432 KB Output is correct
10 Correct 163 ms 428 KB Output is correct
11 Correct 150 ms 428 KB Output is correct
12 Correct 147 ms 428 KB Output is correct
13 Correct 142 ms 420 KB Output is correct
14 Correct 146 ms 460 KB Output is correct
15 Correct 147 ms 340 KB Output is correct
16 Correct 144 ms 424 KB Output is correct
17 Correct 145 ms 408 KB Output is correct