# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
425983 | 2021-06-13T12:43:46 Z | ivan24 | Roller Coaster Railroad (IOI16_railroad) | C++14 | 62 ms | 11112 KB |
#include "railroad.h" #include <bits/stdc++.h> using namespace std; using ll = long long int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vii> vvii; const ll INF = 1e18; long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { int n = (int) s.size(); vvi dp; dp.assign((1 << n),vi(n,INF)); for (ll bm = 1; (1 << n) > bm; bm++){ for (ll lst = 0; n > lst; lst++){ if (((1 << lst) & bm) == 0) continue; if ((bm & -bm) == bm){ dp[bm][lst] = 0; }else{ dp[bm][lst] = INF; ll prvbm = bm - (1 << lst); for (ll prv = 0; n > prv; prv++){ if (prvbm & (1 << prv) == 0) continue; dp[bm][lst] = min(dp[bm][lst],dp[prvbm][prv]+max(0,t[prv]-s[lst])); } //cout << bm << ' ' << lst << ": "; //cout << dp[bm][lst] << endl; } } } ll ans = INF; for (ll i = 0; n > i; i++){ ans = min(ans,dp[(1 << n)-1][i]); } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | n = 2 |
2 | Correct | 1 ms | 204 KB | n = 2 |
3 | Correct | 1 ms | 292 KB | n = 2 |
4 | Correct | 1 ms | 204 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Correct | 1 ms | 204 KB | n = 2 |
7 | Correct | 1 ms | 204 KB | n = 3 |
8 | Correct | 1 ms | 204 KB | n = 3 |
9 | Correct | 1 ms | 288 KB | n = 3 |
10 | Correct | 1 ms | 332 KB | n = 8 |
11 | Correct | 1 ms | 204 KB | n = 8 |
12 | Correct | 1 ms | 292 KB | n = 8 |
13 | Correct | 1 ms | 332 KB | n = 8 |
14 | Correct | 1 ms | 288 KB | n = 8 |
15 | Correct | 1 ms | 204 KB | n = 8 |
16 | Correct | 1 ms | 204 KB | n = 8 |
17 | Correct | 1 ms | 204 KB | n = 8 |
18 | Correct | 1 ms | 204 KB | n = 8 |
19 | Correct | 1 ms | 204 KB | n = 3 |
20 | Correct | 1 ms | 204 KB | n = 7 |
21 | Correct | 1 ms | 204 KB | n = 8 |
22 | Correct | 1 ms | 204 KB | n = 8 |
23 | Correct | 1 ms | 204 KB | n = 8 |
24 | Correct | 1 ms | 288 KB | n = 8 |
25 | Correct | 1 ms | 204 KB | n = 8 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | n = 2 |
2 | Correct | 1 ms | 204 KB | n = 2 |
3 | Correct | 1 ms | 292 KB | n = 2 |
4 | Correct | 1 ms | 204 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Correct | 1 ms | 204 KB | n = 2 |
7 | Correct | 1 ms | 204 KB | n = 3 |
8 | Correct | 1 ms | 204 KB | n = 3 |
9 | Correct | 1 ms | 288 KB | n = 3 |
10 | Correct | 1 ms | 332 KB | n = 8 |
11 | Correct | 1 ms | 204 KB | n = 8 |
12 | Correct | 1 ms | 292 KB | n = 8 |
13 | Correct | 1 ms | 332 KB | n = 8 |
14 | Correct | 1 ms | 288 KB | n = 8 |
15 | Correct | 1 ms | 204 KB | n = 8 |
16 | Correct | 1 ms | 204 KB | n = 8 |
17 | Correct | 1 ms | 204 KB | n = 8 |
18 | Correct | 1 ms | 204 KB | n = 8 |
19 | Correct | 1 ms | 204 KB | n = 3 |
20 | Correct | 1 ms | 204 KB | n = 7 |
21 | Correct | 1 ms | 204 KB | n = 8 |
22 | Correct | 1 ms | 204 KB | n = 8 |
23 | Correct | 1 ms | 204 KB | n = 8 |
24 | Correct | 1 ms | 288 KB | n = 8 |
25 | Correct | 1 ms | 204 KB | n = 8 |
26 | Correct | 1 ms | 204 KB | n = 8 |
27 | Correct | 1 ms | 204 KB | n = 8 |
28 | Correct | 1 ms | 288 KB | n = 8 |
29 | Correct | 55 ms | 11044 KB | n = 16 |
30 | Correct | 47 ms | 11068 KB | n = 16 |
31 | Correct | 45 ms | 10956 KB | n = 16 |
32 | Correct | 44 ms | 10956 KB | n = 16 |
33 | Correct | 45 ms | 11024 KB | n = 16 |
34 | Correct | 46 ms | 11064 KB | n = 16 |
35 | Correct | 44 ms | 11112 KB | n = 16 |
36 | Correct | 20 ms | 5068 KB | n = 15 |
37 | Correct | 1 ms | 204 KB | n = 8 |
38 | Correct | 47 ms | 11028 KB | n = 16 |
39 | Correct | 52 ms | 11068 KB | n = 16 |
40 | Correct | 1 ms | 332 KB | n = 9 |
41 | Correct | 45 ms | 10956 KB | n = 16 |
42 | Correct | 48 ms | 11036 KB | n = 16 |
43 | Correct | 58 ms | 11056 KB | n = 16 |
44 | Correct | 1 ms | 332 KB | n = 9 |
45 | Correct | 21 ms | 5156 KB | n = 15 |
46 | Correct | 43 ms | 10956 KB | n = 16 |
47 | Correct | 45 ms | 11032 KB | n = 16 |
48 | Correct | 45 ms | 10956 KB | n = 16 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 62 ms | 10568 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | n = 2 |
2 | Correct | 1 ms | 204 KB | n = 2 |
3 | Correct | 1 ms | 292 KB | n = 2 |
4 | Correct | 1 ms | 204 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Correct | 1 ms | 204 KB | n = 2 |
7 | Correct | 1 ms | 204 KB | n = 3 |
8 | Correct | 1 ms | 204 KB | n = 3 |
9 | Correct | 1 ms | 288 KB | n = 3 |
10 | Correct | 1 ms | 332 KB | n = 8 |
11 | Correct | 1 ms | 204 KB | n = 8 |
12 | Correct | 1 ms | 292 KB | n = 8 |
13 | Correct | 1 ms | 332 KB | n = 8 |
14 | Correct | 1 ms | 288 KB | n = 8 |
15 | Correct | 1 ms | 204 KB | n = 8 |
16 | Correct | 1 ms | 204 KB | n = 8 |
17 | Correct | 1 ms | 204 KB | n = 8 |
18 | Correct | 1 ms | 204 KB | n = 8 |
19 | Correct | 1 ms | 204 KB | n = 3 |
20 | Correct | 1 ms | 204 KB | n = 7 |
21 | Correct | 1 ms | 204 KB | n = 8 |
22 | Correct | 1 ms | 204 KB | n = 8 |
23 | Correct | 1 ms | 204 KB | n = 8 |
24 | Correct | 1 ms | 288 KB | n = 8 |
25 | Correct | 1 ms | 204 KB | n = 8 |
26 | Correct | 1 ms | 204 KB | n = 8 |
27 | Correct | 1 ms | 204 KB | n = 8 |
28 | Correct | 1 ms | 288 KB | n = 8 |
29 | Correct | 55 ms | 11044 KB | n = 16 |
30 | Correct | 47 ms | 11068 KB | n = 16 |
31 | Correct | 45 ms | 10956 KB | n = 16 |
32 | Correct | 44 ms | 10956 KB | n = 16 |
33 | Correct | 45 ms | 11024 KB | n = 16 |
34 | Correct | 46 ms | 11064 KB | n = 16 |
35 | Correct | 44 ms | 11112 KB | n = 16 |
36 | Correct | 20 ms | 5068 KB | n = 15 |
37 | Correct | 1 ms | 204 KB | n = 8 |
38 | Correct | 47 ms | 11028 KB | n = 16 |
39 | Correct | 52 ms | 11068 KB | n = 16 |
40 | Correct | 1 ms | 332 KB | n = 9 |
41 | Correct | 45 ms | 10956 KB | n = 16 |
42 | Correct | 48 ms | 11036 KB | n = 16 |
43 | Correct | 58 ms | 11056 KB | n = 16 |
44 | Correct | 1 ms | 332 KB | n = 9 |
45 | Correct | 21 ms | 5156 KB | n = 15 |
46 | Correct | 43 ms | 10956 KB | n = 16 |
47 | Correct | 45 ms | 11032 KB | n = 16 |
48 | Correct | 45 ms | 10956 KB | n = 16 |
49 | Runtime error | 62 ms | 10568 KB | Execution killed with signal 6 |
50 | Halted | 0 ms | 0 KB | - |