Submission #114629

# Submission time Handle Problem Language Result Execution time Memory
114629 2019-06-02T05:54:53 Z E869120 Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
67 ms 9848 KB
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

long long N, A[100009], B[100009], dp[1 << 16][17];

long long plan_roller_coaster(vector<int>s, vector<int>t) {
	N = s.size();
	for (int i = 0; i < N; i++) { A[i] = s[i]; B[i] = t[i]; }
	for (int i = 0; i < (1 << N); i++) { for (int j = 0; j <= N; j++) dp[i][j] = (1LL << 60); }
	
	dp[0][N] = 0; B[N] = 1;
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j <= N; j++) {
			if (dp[i][j] == (1LL << 60)) continue;
			for (int k = 0; k < N; k++) {
				if ((i & (1 << k)) != 0) continue;
				dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + max(0LL, B[j] - A[k]));
			}
		}
	}
    long long minx = (1LL << 60);
    for (int i = 0; i < N; i++) minx = min(minx, dp[(1 << N) - 1][i]);
    return minx;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 256 KB n = 2
3 Correct 2 ms 256 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 384 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 384 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 2 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 256 KB n = 2
3 Correct 2 ms 256 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 384 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 384 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 2 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 384 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 2 ms 384 KB n = 8
29 Correct 44 ms 9088 KB n = 16
30 Correct 39 ms 9088 KB n = 16
31 Correct 41 ms 9088 KB n = 16
32 Correct 39 ms 9088 KB n = 16
33 Correct 39 ms 9016 KB n = 16
34 Correct 39 ms 9080 KB n = 16
35 Correct 40 ms 9088 KB n = 16
36 Correct 20 ms 4728 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 41 ms 9088 KB n = 16
39 Correct 41 ms 9088 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 40 ms 9088 KB n = 16
42 Correct 40 ms 9208 KB n = 16
43 Correct 40 ms 9088 KB n = 16
44 Correct 2 ms 384 KB n = 9
45 Correct 20 ms 4736 KB n = 15
46 Correct 39 ms 9088 KB n = 16
47 Correct 38 ms 9088 KB n = 16
48 Correct 38 ms 9088 KB n = 16
# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 256 KB n = 2
3 Correct 2 ms 256 KB n = 2
4 Correct 2 ms 384 KB n = 2
5 Correct 2 ms 384 KB n = 2
6 Correct 2 ms 384 KB n = 2
7 Correct 2 ms 384 KB n = 3
8 Correct 2 ms 384 KB n = 3
9 Correct 2 ms 384 KB n = 3
10 Correct 2 ms 384 KB n = 8
11 Correct 2 ms 384 KB n = 8
12 Correct 2 ms 384 KB n = 8
13 Correct 2 ms 384 KB n = 8
14 Correct 2 ms 384 KB n = 8
15 Correct 2 ms 384 KB n = 8
16 Correct 2 ms 384 KB n = 8
17 Correct 2 ms 384 KB n = 8
18 Correct 2 ms 384 KB n = 8
19 Correct 2 ms 384 KB n = 3
20 Correct 2 ms 384 KB n = 7
21 Correct 2 ms 384 KB n = 8
22 Correct 2 ms 384 KB n = 8
23 Correct 2 ms 384 KB n = 8
24 Correct 2 ms 384 KB n = 8
25 Correct 2 ms 384 KB n = 8
26 Correct 2 ms 384 KB n = 8
27 Correct 2 ms 384 KB n = 8
28 Correct 2 ms 384 KB n = 8
29 Correct 44 ms 9088 KB n = 16
30 Correct 39 ms 9088 KB n = 16
31 Correct 41 ms 9088 KB n = 16
32 Correct 39 ms 9088 KB n = 16
33 Correct 39 ms 9016 KB n = 16
34 Correct 39 ms 9080 KB n = 16
35 Correct 40 ms 9088 KB n = 16
36 Correct 20 ms 4728 KB n = 15
37 Correct 2 ms 384 KB n = 8
38 Correct 41 ms 9088 KB n = 16
39 Correct 41 ms 9088 KB n = 16
40 Correct 2 ms 384 KB n = 9
41 Correct 40 ms 9088 KB n = 16
42 Correct 40 ms 9208 KB n = 16
43 Correct 40 ms 9088 KB n = 16
44 Correct 2 ms 384 KB n = 9
45 Correct 20 ms 4736 KB n = 15
46 Correct 39 ms 9088 KB n = 16
47 Correct 38 ms 9088 KB n = 16
48 Correct 38 ms 9088 KB n = 16
49 Runtime error 67 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -