#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
long long adj[20][20];
long long memo[20][66000];
long long tsp(int x,int bm){
if(memo[x][bm]!=-1)return memo[x][bm];
if(bm==0)return memo[x][bm]=0;
long long ans=1000000000000000010;
int bm2=bm;
while(bm2&(-bm2)){
int y=__builtin_ctz(bm2);
ans=min(ans,tsp(y,bm-(bm2&(-bm2)))+adj[x][y]);
bm2-=(bm2&(-bm2));
}
return memo[x][bm]=ans;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n=(int)s.size();
if(n>16){
vector<pair<int,int> > S,T;
for(int i=0;i<n;i++){
S.push_back(make_pair(s[i],i));
T.push_back(make_pair(t[i],i));
}
sort(S.begin(),S.end()); sort(T.begin(),T.end());
int pos[n];
for(int i=0;i<n;i++){
pos[S[i].second]=i;
}
for(int i=n-1;i>=0;i--){
if(pos[T[i].second]>=i){
if(s[T[i].second-1]<T[i].first){
return 1;
}
///do something with T[i].second-1
}else{
if(s[T[i].second]<T[i].first){
return 1;
}
///do something with T[i].second
}
}
return 0;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)adj[i][j]=0;
else adj[i][j]=max(0,t[i]-s[j]);
}
}
memset(memo,-1,sizeof(memo));
long long ans=4000000000000000010;
for(int i=0;i<n;i++){
ans=min(ans,tsp(i,(1<<n)-1-(1<<i)));
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10624 KB |
n = 2 |
2 |
Correct |
11 ms |
10624 KB |
n = 2 |
3 |
Correct |
11 ms |
10600 KB |
n = 2 |
4 |
Correct |
11 ms |
10624 KB |
n = 2 |
5 |
Correct |
10 ms |
10624 KB |
n = 2 |
6 |
Correct |
11 ms |
10624 KB |
n = 2 |
7 |
Correct |
10 ms |
10624 KB |
n = 3 |
8 |
Correct |
11 ms |
10624 KB |
n = 3 |
9 |
Correct |
11 ms |
10624 KB |
n = 3 |
10 |
Correct |
10 ms |
10624 KB |
n = 8 |
11 |
Correct |
12 ms |
10624 KB |
n = 8 |
12 |
Correct |
13 ms |
10752 KB |
n = 8 |
13 |
Correct |
10 ms |
10624 KB |
n = 8 |
14 |
Correct |
10 ms |
10708 KB |
n = 8 |
15 |
Correct |
12 ms |
10624 KB |
n = 8 |
16 |
Correct |
12 ms |
10624 KB |
n = 8 |
17 |
Correct |
10 ms |
10624 KB |
n = 8 |
18 |
Correct |
11 ms |
10624 KB |
n = 8 |
19 |
Correct |
12 ms |
10624 KB |
n = 3 |
20 |
Correct |
11 ms |
10624 KB |
n = 7 |
21 |
Correct |
14 ms |
10624 KB |
n = 8 |
22 |
Correct |
13 ms |
10624 KB |
n = 8 |
23 |
Correct |
11 ms |
10624 KB |
n = 8 |
24 |
Correct |
11 ms |
10624 KB |
n = 8 |
25 |
Correct |
11 ms |
10624 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10624 KB |
n = 2 |
2 |
Correct |
11 ms |
10624 KB |
n = 2 |
3 |
Correct |
11 ms |
10600 KB |
n = 2 |
4 |
Correct |
11 ms |
10624 KB |
n = 2 |
5 |
Correct |
10 ms |
10624 KB |
n = 2 |
6 |
Correct |
11 ms |
10624 KB |
n = 2 |
7 |
Correct |
10 ms |
10624 KB |
n = 3 |
8 |
Correct |
11 ms |
10624 KB |
n = 3 |
9 |
Correct |
11 ms |
10624 KB |
n = 3 |
10 |
Correct |
10 ms |
10624 KB |
n = 8 |
11 |
Correct |
12 ms |
10624 KB |
n = 8 |
12 |
Correct |
13 ms |
10752 KB |
n = 8 |
13 |
Correct |
10 ms |
10624 KB |
n = 8 |
14 |
Correct |
10 ms |
10708 KB |
n = 8 |
15 |
Correct |
12 ms |
10624 KB |
n = 8 |
16 |
Correct |
12 ms |
10624 KB |
n = 8 |
17 |
Correct |
10 ms |
10624 KB |
n = 8 |
18 |
Correct |
11 ms |
10624 KB |
n = 8 |
19 |
Correct |
12 ms |
10624 KB |
n = 3 |
20 |
Correct |
11 ms |
10624 KB |
n = 7 |
21 |
Correct |
14 ms |
10624 KB |
n = 8 |
22 |
Correct |
13 ms |
10624 KB |
n = 8 |
23 |
Correct |
11 ms |
10624 KB |
n = 8 |
24 |
Correct |
11 ms |
10624 KB |
n = 8 |
25 |
Correct |
11 ms |
10624 KB |
n = 8 |
26 |
Correct |
10 ms |
10624 KB |
n = 8 |
27 |
Correct |
11 ms |
10624 KB |
n = 8 |
28 |
Correct |
11 ms |
10624 KB |
n = 8 |
29 |
Correct |
58 ms |
10744 KB |
n = 16 |
30 |
Correct |
77 ms |
10752 KB |
n = 16 |
31 |
Correct |
83 ms |
10624 KB |
n = 16 |
32 |
Correct |
49 ms |
10596 KB |
n = 16 |
33 |
Correct |
69 ms |
10624 KB |
n = 16 |
34 |
Correct |
46 ms |
10624 KB |
n = 16 |
35 |
Correct |
85 ms |
10688 KB |
n = 16 |
36 |
Correct |
27 ms |
10624 KB |
n = 15 |
37 |
Correct |
12 ms |
10624 KB |
n = 8 |
38 |
Correct |
55 ms |
10624 KB |
n = 16 |
39 |
Correct |
47 ms |
10624 KB |
n = 16 |
40 |
Correct |
12 ms |
10624 KB |
n = 9 |
41 |
Correct |
65 ms |
10624 KB |
n = 16 |
42 |
Correct |
63 ms |
10624 KB |
n = 16 |
43 |
Correct |
69 ms |
10724 KB |
n = 16 |
44 |
Correct |
11 ms |
10624 KB |
n = 9 |
45 |
Correct |
29 ms |
10624 KB |
n = 15 |
46 |
Correct |
59 ms |
10688 KB |
n = 16 |
47 |
Correct |
51 ms |
10624 KB |
n = 16 |
48 |
Correct |
61 ms |
10624 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
129 ms |
7544 KB |
answer is not correct: 1 instead of 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10624 KB |
n = 2 |
2 |
Correct |
11 ms |
10624 KB |
n = 2 |
3 |
Correct |
11 ms |
10600 KB |
n = 2 |
4 |
Correct |
11 ms |
10624 KB |
n = 2 |
5 |
Correct |
10 ms |
10624 KB |
n = 2 |
6 |
Correct |
11 ms |
10624 KB |
n = 2 |
7 |
Correct |
10 ms |
10624 KB |
n = 3 |
8 |
Correct |
11 ms |
10624 KB |
n = 3 |
9 |
Correct |
11 ms |
10624 KB |
n = 3 |
10 |
Correct |
10 ms |
10624 KB |
n = 8 |
11 |
Correct |
12 ms |
10624 KB |
n = 8 |
12 |
Correct |
13 ms |
10752 KB |
n = 8 |
13 |
Correct |
10 ms |
10624 KB |
n = 8 |
14 |
Correct |
10 ms |
10708 KB |
n = 8 |
15 |
Correct |
12 ms |
10624 KB |
n = 8 |
16 |
Correct |
12 ms |
10624 KB |
n = 8 |
17 |
Correct |
10 ms |
10624 KB |
n = 8 |
18 |
Correct |
11 ms |
10624 KB |
n = 8 |
19 |
Correct |
12 ms |
10624 KB |
n = 3 |
20 |
Correct |
11 ms |
10624 KB |
n = 7 |
21 |
Correct |
14 ms |
10624 KB |
n = 8 |
22 |
Correct |
13 ms |
10624 KB |
n = 8 |
23 |
Correct |
11 ms |
10624 KB |
n = 8 |
24 |
Correct |
11 ms |
10624 KB |
n = 8 |
25 |
Correct |
11 ms |
10624 KB |
n = 8 |
26 |
Correct |
10 ms |
10624 KB |
n = 8 |
27 |
Correct |
11 ms |
10624 KB |
n = 8 |
28 |
Correct |
11 ms |
10624 KB |
n = 8 |
29 |
Correct |
58 ms |
10744 KB |
n = 16 |
30 |
Correct |
77 ms |
10752 KB |
n = 16 |
31 |
Correct |
83 ms |
10624 KB |
n = 16 |
32 |
Correct |
49 ms |
10596 KB |
n = 16 |
33 |
Correct |
69 ms |
10624 KB |
n = 16 |
34 |
Correct |
46 ms |
10624 KB |
n = 16 |
35 |
Correct |
85 ms |
10688 KB |
n = 16 |
36 |
Correct |
27 ms |
10624 KB |
n = 15 |
37 |
Correct |
12 ms |
10624 KB |
n = 8 |
38 |
Correct |
55 ms |
10624 KB |
n = 16 |
39 |
Correct |
47 ms |
10624 KB |
n = 16 |
40 |
Correct |
12 ms |
10624 KB |
n = 9 |
41 |
Correct |
65 ms |
10624 KB |
n = 16 |
42 |
Correct |
63 ms |
10624 KB |
n = 16 |
43 |
Correct |
69 ms |
10724 KB |
n = 16 |
44 |
Correct |
11 ms |
10624 KB |
n = 9 |
45 |
Correct |
29 ms |
10624 KB |
n = 15 |
46 |
Correct |
59 ms |
10688 KB |
n = 16 |
47 |
Correct |
51 ms |
10624 KB |
n = 16 |
48 |
Correct |
61 ms |
10624 KB |
n = 16 |
49 |
Incorrect |
129 ms |
7544 KB |
answer is not correct: 1 instead of 0 |
50 |
Halted |
0 ms |
0 KB |
- |