답안 #336711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336711	2020-12-16T13:05:02 Z	nandonathaniel	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	61 ms	10860 KB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
LL dp[(1<<16)][16];
 
 
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
	for(LL i=0;i<(1<<n);i++){
		for(LL j=0;j<n;j++){
			dp[i][j]=INF;
		}
	}
    for(LL i=0;i<n;i++)dp[(1<<i)][i]=0;
    for(LL i=0;i<(1<<n);i++){
    	for(LL j=0;j<n;j++){
    		if(i & (1<<j)){
    			for(LL k=0;k<n;k++){
    				if(!(i & (1<<k))){
    					dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+max(t[j]-s[k],0));
					}
				}
			}
		}
	}
	LL ans=INF;
	for(LL i=0;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]);
    return ans;
}

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	n = 2
2	Correct	1 ms	364 KB	n = 2
3	Correct	1 ms	364 KB	n = 2
4	Correct	1 ms	364 KB	n = 2
5	Correct	1 ms	364 KB	n = 2
6	Correct	1 ms	364 KB	n = 2
7	Correct	1 ms	364 KB	n = 3
8	Correct	1 ms	364 KB	n = 3
9	Correct	1 ms	364 KB	n = 3
10	Correct	1 ms	364 KB	n = 8
11	Correct	1 ms	364 KB	n = 8
12	Correct	1 ms	364 KB	n = 8
13	Correct	1 ms	364 KB	n = 8
14	Correct	1 ms	364 KB	n = 8
15	Correct	1 ms	364 KB	n = 8
16	Correct	1 ms	364 KB	n = 8
17	Correct	1 ms	364 KB	n = 8
18	Correct	1 ms	384 KB	n = 8
19	Correct	1 ms	364 KB	n = 3
20	Correct	1 ms	364 KB	n = 7
21	Correct	1 ms	364 KB	n = 8
22	Correct	1 ms	364 KB	n = 8
23	Correct	1 ms	364 KB	n = 8
24	Correct	1 ms	364 KB	n = 8
25	Correct	1 ms	364 KB	n = 8

Subtask #2

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	n = 2
2	Correct	1 ms	364 KB	n = 2
3	Correct	1 ms	364 KB	n = 2
4	Correct	1 ms	364 KB	n = 2
5	Correct	1 ms	364 KB	n = 2
6	Correct	1 ms	364 KB	n = 2
7	Correct	1 ms	364 KB	n = 3
8	Correct	1 ms	364 KB	n = 3
9	Correct	1 ms	364 KB	n = 3
10	Correct	1 ms	364 KB	n = 8
11	Correct	1 ms	364 KB	n = 8
12	Correct	1 ms	364 KB	n = 8
13	Correct	1 ms	364 KB	n = 8
14	Correct	1 ms	364 KB	n = 8
15	Correct	1 ms	364 KB	n = 8
16	Correct	1 ms	364 KB	n = 8
17	Correct	1 ms	364 KB	n = 8
18	Correct	1 ms	384 KB	n = 8
19	Correct	1 ms	364 KB	n = 3
20	Correct	1 ms	364 KB	n = 7
21	Correct	1 ms	364 KB	n = 8
22	Correct	1 ms	364 KB	n = 8
23	Correct	1 ms	364 KB	n = 8
24	Correct	1 ms	364 KB	n = 8
25	Correct	1 ms	364 KB	n = 8
26	Correct	1 ms	364 KB	n = 8
27	Correct	1 ms	364 KB	n = 8
28	Correct	1 ms	364 KB	n = 8
29	Correct	35 ms	8556 KB	n = 16
30	Correct	39 ms	8684 KB	n = 16
31	Correct	36 ms	8684 KB	n = 16
32	Correct	36 ms	8556 KB	n = 16
33	Correct	38 ms	8556 KB	n = 16
34	Correct	35 ms	8556 KB	n = 16
35	Correct	35 ms	8556 KB	n = 16
36	Correct	17 ms	4588 KB	n = 15
37	Correct	1 ms	364 KB	n = 8
38	Correct	40 ms	8556 KB	n = 16
39	Correct	40 ms	8556 KB	n = 16
40	Correct	1 ms	364 KB	n = 9
41	Correct	36 ms	8572 KB	n = 16
42	Correct	43 ms	8556 KB	n = 16
43	Correct	42 ms	8588 KB	n = 16
44	Correct	1 ms	364 KB	n = 9
45	Correct	17 ms	4460 KB	n = 15
46	Correct	36 ms	8556 KB	n = 16
47	Correct	36 ms	8556 KB	n = 16
48	Correct	37 ms	8556 KB	n = 16

Subtask #3

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	61 ms	10860 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	n = 2
2	Correct	1 ms	364 KB	n = 2
3	Correct	1 ms	364 KB	n = 2
4	Correct	1 ms	364 KB	n = 2
5	Correct	1 ms	364 KB	n = 2
6	Correct	1 ms	364 KB	n = 2
7	Correct	1 ms	364 KB	n = 3
8	Correct	1 ms	364 KB	n = 3
9	Correct	1 ms	364 KB	n = 3
10	Correct	1 ms	364 KB	n = 8
11	Correct	1 ms	364 KB	n = 8
12	Correct	1 ms	364 KB	n = 8
13	Correct	1 ms	364 KB	n = 8
14	Correct	1 ms	364 KB	n = 8
15	Correct	1 ms	364 KB	n = 8
16	Correct	1 ms	364 KB	n = 8
17	Correct	1 ms	364 KB	n = 8
18	Correct	1 ms	384 KB	n = 8
19	Correct	1 ms	364 KB	n = 3
20	Correct	1 ms	364 KB	n = 7
21	Correct	1 ms	364 KB	n = 8
22	Correct	1 ms	364 KB	n = 8
23	Correct	1 ms	364 KB	n = 8
24	Correct	1 ms	364 KB	n = 8
25	Correct	1 ms	364 KB	n = 8
26	Correct	1 ms	364 KB	n = 8
27	Correct	1 ms	364 KB	n = 8
28	Correct	1 ms	364 KB	n = 8
29	Correct	35 ms	8556 KB	n = 16
30	Correct	39 ms	8684 KB	n = 16
31	Correct	36 ms	8684 KB	n = 16
32	Correct	36 ms	8556 KB	n = 16
33	Correct	38 ms	8556 KB	n = 16
34	Correct	35 ms	8556 KB	n = 16
35	Correct	35 ms	8556 KB	n = 16
36	Correct	17 ms	4588 KB	n = 15
37	Correct	1 ms	364 KB	n = 8
38	Correct	40 ms	8556 KB	n = 16
39	Correct	40 ms	8556 KB	n = 16
40	Correct	1 ms	364 KB	n = 9
41	Correct	36 ms	8572 KB	n = 16
42	Correct	43 ms	8556 KB	n = 16
43	Correct	42 ms	8588 KB	n = 16
44	Correct	1 ms	364 KB	n = 9
45	Correct	17 ms	4460 KB	n = 15
46	Correct	36 ms	8556 KB	n = 16
47	Correct	36 ms	8556 KB	n = 16
48	Correct	37 ms	8556 KB	n = 16
49	Runtime error	61 ms	10860 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Halted	0 ms	0 KB	-