Submission #24497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24497	2017-06-09T12:09:32 Z	Donghyun Kim(#1043)	Roller Coaster Railroad (IOI16_railroad)	C++14	11 / 100	2000 ms	18212 KB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, S[17], T[17], chk[17][65536];
ll dp[17][65536];
const ll inf = 1e18;

ll f(int x, int st){
    if(!st) return 0;
    dp[x][st] = inf;
    for(int i = 0; i < n; i++){
		if((1 << i) & st){
			dp[x][st] = min(dp[x][st], f(i, st - (1 << i)) + (ll)max(0, T[x] - S[i]));
		}
    }
    return dp[x][st];
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int)s.size();
	for(int i = 0; i < n; i++){ S[i] = s[i]; T[i] = t[i]; }
	T[n] = 1;
	return f(n, (1 << n) - 1);
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	15076 KB	n = 2
2	Correct	0 ms	15076 KB	n = 2
3	Correct	0 ms	15076 KB	n = 2
4	Correct	0 ms	15076 KB	n = 2
5	Correct	0 ms	15076 KB	n = 2
6	Correct	0 ms	15076 KB	n = 2
7	Correct	0 ms	15076 KB	n = 3
8	Correct	0 ms	15076 KB	n = 3
9	Correct	0 ms	15076 KB	n = 3
10	Correct	0 ms	15076 KB	n = 8
11	Correct	3 ms	15076 KB	n = 8
12	Correct	0 ms	15076 KB	n = 8
13	Correct	0 ms	15076 KB	n = 8
14	Correct	0 ms	15076 KB	n = 8
15	Correct	0 ms	15076 KB	n = 8
16	Correct	0 ms	15076 KB	n = 8
17	Correct	0 ms	15076 KB	n = 8
18	Correct	0 ms	15076 KB	n = 8
19	Correct	0 ms	15076 KB	n = 3
20	Correct	0 ms	15076 KB	n = 7
21	Correct	0 ms	15076 KB	n = 8
22	Correct	0 ms	15076 KB	n = 8
23	Correct	3 ms	15076 KB	n = 8
24	Correct	0 ms	15076 KB	n = 8
25	Correct	0 ms	15076 KB	n = 8

Subtask #2

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	15076 KB	n = 2
2	Correct	0 ms	15076 KB	n = 2
3	Correct	0 ms	15076 KB	n = 2
4	Correct	0 ms	15076 KB	n = 2
5	Correct	0 ms	15076 KB	n = 2
6	Correct	0 ms	15076 KB	n = 2
7	Correct	0 ms	15076 KB	n = 3
8	Correct	0 ms	15076 KB	n = 3
9	Correct	0 ms	15076 KB	n = 3
10	Correct	0 ms	15076 KB	n = 8
11	Correct	3 ms	15076 KB	n = 8
12	Correct	0 ms	15076 KB	n = 8
13	Correct	0 ms	15076 KB	n = 8
14	Correct	0 ms	15076 KB	n = 8
15	Correct	0 ms	15076 KB	n = 8
16	Correct	0 ms	15076 KB	n = 8
17	Correct	0 ms	15076 KB	n = 8
18	Correct	0 ms	15076 KB	n = 8
19	Correct	0 ms	15076 KB	n = 3
20	Correct	0 ms	15076 KB	n = 7
21	Correct	0 ms	15076 KB	n = 8
22	Correct	0 ms	15076 KB	n = 8
23	Correct	3 ms	15076 KB	n = 8
24	Correct	0 ms	15076 KB	n = 8
25	Correct	0 ms	15076 KB	n = 8
26	Correct	0 ms	15076 KB	n = 8
27	Correct	0 ms	15076 KB	n = 8
28	Correct	0 ms	15076 KB	n = 8
29	Execution timed out	2000 ms	15076 KB	Execution timed out
30	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	99 ms	18212 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	15076 KB	n = 2
2	Correct	0 ms	15076 KB	n = 2
3	Correct	0 ms	15076 KB	n = 2
4	Correct	0 ms	15076 KB	n = 2
5	Correct	0 ms	15076 KB	n = 2
6	Correct	0 ms	15076 KB	n = 2
7	Correct	0 ms	15076 KB	n = 3
8	Correct	0 ms	15076 KB	n = 3
9	Correct	0 ms	15076 KB	n = 3
10	Correct	0 ms	15076 KB	n = 8
11	Correct	3 ms	15076 KB	n = 8
12	Correct	0 ms	15076 KB	n = 8
13	Correct	0 ms	15076 KB	n = 8
14	Correct	0 ms	15076 KB	n = 8
15	Correct	0 ms	15076 KB	n = 8
16	Correct	0 ms	15076 KB	n = 8
17	Correct	0 ms	15076 KB	n = 8
18	Correct	0 ms	15076 KB	n = 8
19	Correct	0 ms	15076 KB	n = 3
20	Correct	0 ms	15076 KB	n = 7
21	Correct	0 ms	15076 KB	n = 8
22	Correct	0 ms	15076 KB	n = 8
23	Correct	3 ms	15076 KB	n = 8
24	Correct	0 ms	15076 KB	n = 8
25	Correct	0 ms	15076 KB	n = 8
26	Correct	0 ms	15076 KB	n = 8
27	Correct	0 ms	15076 KB	n = 8
28	Correct	0 ms	15076 KB	n = 8
29	Execution timed out	2000 ms	15076 KB	Execution timed out
30	Halted	0 ms	0 KB	-