#include "railroad.h"
#include <bits/stdc++.h>
#define INF 1e18
using namespace std;
typedef pair<int,int> ii;
int n;
vector<int> s, t;
long long memo[17][65537];
long long dp(int id, int mask){
//printf("%lld %lld\n",id,mask);
if (mask == (1<<n) - 1) return 0;
if (memo[id][mask] != -1) return memo[id][mask];
memo[id][mask] = INF;
for (int i = 0; i < n; i++){
if (!(mask&(1<<i))){
memo[id][mask] = min(memo[id][mask],dp(i,(mask|(1<<i)))+max(0,t[id]-s[i]));
}
}
return memo[id][mask];
}
long long plan_roller_coaster(vector<int> t1, vector<int> t2) {
n = (int) t1.size();
for (int i = 0; i < n; i++){
s.push_back(t1[i]);
t.push_back(t2[i]);
}
vector<ii> s0,t0;
for (int i = 1; i <= n; i++){
s0.push_back(ii(t1[i-1],i));
t0.push_back(ii(t2[i-1],i));
}
s0.push_back(ii(1000000001,n+1));
t0.push_back(ii(0,0));
long long ans = INF;
if (n <= 16){
memset(memo,-1,sizeof(memo));
for (int i = 0; i < n; i++){
ans = min(ans,dp(i,1<<i));
}
}
else{
sort(s0.begin(),s0.end(),greater<ii>());
sort(t0.begin(),t0.end(),greater<ii>());
int order[n+2];
for (int i = 0; i < t0.size(); i++){
//printf("%d -> %d\n", t0[i].second, s0[i].second);
if (t0[i].first > s0[i].first) {
return 1;
}
order[t0[i].second] = s0[i].second;
}
int cur = -1;
int curid = 0;
while (curid != n+1){
//printf("%d\n",curid);
curid = order[curid];
cur++;
}
//printf("%d\n",cur);
if (cur != n) return 1;
return 0;
}
return ans;
}
Compilation message
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t0.size(); i++){
~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
9088 KB |
n = 2 |
2 |
Correct |
8 ms |
9088 KB |
n = 2 |
3 |
Correct |
9 ms |
9088 KB |
n = 2 |
4 |
Correct |
10 ms |
9088 KB |
n = 2 |
5 |
Correct |
8 ms |
9088 KB |
n = 2 |
6 |
Correct |
10 ms |
9088 KB |
n = 2 |
7 |
Correct |
9 ms |
9088 KB |
n = 3 |
8 |
Correct |
9 ms |
9088 KB |
n = 3 |
9 |
Correct |
8 ms |
9088 KB |
n = 3 |
10 |
Correct |
9 ms |
9088 KB |
n = 8 |
11 |
Correct |
8 ms |
9088 KB |
n = 8 |
12 |
Correct |
8 ms |
9088 KB |
n = 8 |
13 |
Correct |
9 ms |
9088 KB |
n = 8 |
14 |
Correct |
11 ms |
9088 KB |
n = 8 |
15 |
Correct |
9 ms |
9088 KB |
n = 8 |
16 |
Correct |
11 ms |
9088 KB |
n = 8 |
17 |
Correct |
9 ms |
9088 KB |
n = 8 |
18 |
Correct |
10 ms |
9088 KB |
n = 8 |
19 |
Correct |
9 ms |
9088 KB |
n = 3 |
20 |
Correct |
11 ms |
9088 KB |
n = 7 |
21 |
Correct |
9 ms |
9088 KB |
n = 8 |
22 |
Correct |
9 ms |
9088 KB |
n = 8 |
23 |
Correct |
9 ms |
9088 KB |
n = 8 |
24 |
Correct |
9 ms |
9088 KB |
n = 8 |
25 |
Correct |
9 ms |
9088 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
9088 KB |
n = 2 |
2 |
Correct |
8 ms |
9088 KB |
n = 2 |
3 |
Correct |
9 ms |
9088 KB |
n = 2 |
4 |
Correct |
10 ms |
9088 KB |
n = 2 |
5 |
Correct |
8 ms |
9088 KB |
n = 2 |
6 |
Correct |
10 ms |
9088 KB |
n = 2 |
7 |
Correct |
9 ms |
9088 KB |
n = 3 |
8 |
Correct |
9 ms |
9088 KB |
n = 3 |
9 |
Correct |
8 ms |
9088 KB |
n = 3 |
10 |
Correct |
9 ms |
9088 KB |
n = 8 |
11 |
Correct |
8 ms |
9088 KB |
n = 8 |
12 |
Correct |
8 ms |
9088 KB |
n = 8 |
13 |
Correct |
9 ms |
9088 KB |
n = 8 |
14 |
Correct |
11 ms |
9088 KB |
n = 8 |
15 |
Correct |
9 ms |
9088 KB |
n = 8 |
16 |
Correct |
11 ms |
9088 KB |
n = 8 |
17 |
Correct |
9 ms |
9088 KB |
n = 8 |
18 |
Correct |
10 ms |
9088 KB |
n = 8 |
19 |
Correct |
9 ms |
9088 KB |
n = 3 |
20 |
Correct |
11 ms |
9088 KB |
n = 7 |
21 |
Correct |
9 ms |
9088 KB |
n = 8 |
22 |
Correct |
9 ms |
9088 KB |
n = 8 |
23 |
Correct |
9 ms |
9088 KB |
n = 8 |
24 |
Correct |
9 ms |
9088 KB |
n = 8 |
25 |
Correct |
9 ms |
9088 KB |
n = 8 |
26 |
Correct |
9 ms |
9088 KB |
n = 8 |
27 |
Correct |
9 ms |
9088 KB |
n = 8 |
28 |
Correct |
8 ms |
9088 KB |
n = 8 |
29 |
Correct |
136 ms |
9076 KB |
n = 16 |
30 |
Correct |
133 ms |
9088 KB |
n = 16 |
31 |
Correct |
105 ms |
9080 KB |
n = 16 |
32 |
Correct |
153 ms |
9088 KB |
n = 16 |
33 |
Correct |
155 ms |
9060 KB |
n = 16 |
34 |
Correct |
177 ms |
9080 KB |
n = 16 |
35 |
Correct |
194 ms |
9088 KB |
n = 16 |
36 |
Correct |
62 ms |
9088 KB |
n = 15 |
37 |
Correct |
11 ms |
9088 KB |
n = 8 |
38 |
Correct |
141 ms |
9080 KB |
n = 16 |
39 |
Correct |
150 ms |
9080 KB |
n = 16 |
40 |
Correct |
9 ms |
9088 KB |
n = 9 |
41 |
Correct |
151 ms |
9080 KB |
n = 16 |
42 |
Correct |
144 ms |
9180 KB |
n = 16 |
43 |
Correct |
134 ms |
9080 KB |
n = 16 |
44 |
Correct |
11 ms |
9088 KB |
n = 9 |
45 |
Correct |
74 ms |
9080 KB |
n = 15 |
46 |
Correct |
138 ms |
9080 KB |
n = 16 |
47 |
Correct |
147 ms |
9084 KB |
n = 16 |
48 |
Correct |
147 ms |
9088 KB |
n = 16 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
123 ms |
9136 KB |
answer is not correct: 1 instead of 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
9088 KB |
n = 2 |
2 |
Correct |
8 ms |
9088 KB |
n = 2 |
3 |
Correct |
9 ms |
9088 KB |
n = 2 |
4 |
Correct |
10 ms |
9088 KB |
n = 2 |
5 |
Correct |
8 ms |
9088 KB |
n = 2 |
6 |
Correct |
10 ms |
9088 KB |
n = 2 |
7 |
Correct |
9 ms |
9088 KB |
n = 3 |
8 |
Correct |
9 ms |
9088 KB |
n = 3 |
9 |
Correct |
8 ms |
9088 KB |
n = 3 |
10 |
Correct |
9 ms |
9088 KB |
n = 8 |
11 |
Correct |
8 ms |
9088 KB |
n = 8 |
12 |
Correct |
8 ms |
9088 KB |
n = 8 |
13 |
Correct |
9 ms |
9088 KB |
n = 8 |
14 |
Correct |
11 ms |
9088 KB |
n = 8 |
15 |
Correct |
9 ms |
9088 KB |
n = 8 |
16 |
Correct |
11 ms |
9088 KB |
n = 8 |
17 |
Correct |
9 ms |
9088 KB |
n = 8 |
18 |
Correct |
10 ms |
9088 KB |
n = 8 |
19 |
Correct |
9 ms |
9088 KB |
n = 3 |
20 |
Correct |
11 ms |
9088 KB |
n = 7 |
21 |
Correct |
9 ms |
9088 KB |
n = 8 |
22 |
Correct |
9 ms |
9088 KB |
n = 8 |
23 |
Correct |
9 ms |
9088 KB |
n = 8 |
24 |
Correct |
9 ms |
9088 KB |
n = 8 |
25 |
Correct |
9 ms |
9088 KB |
n = 8 |
26 |
Correct |
9 ms |
9088 KB |
n = 8 |
27 |
Correct |
9 ms |
9088 KB |
n = 8 |
28 |
Correct |
8 ms |
9088 KB |
n = 8 |
29 |
Correct |
136 ms |
9076 KB |
n = 16 |
30 |
Correct |
133 ms |
9088 KB |
n = 16 |
31 |
Correct |
105 ms |
9080 KB |
n = 16 |
32 |
Correct |
153 ms |
9088 KB |
n = 16 |
33 |
Correct |
155 ms |
9060 KB |
n = 16 |
34 |
Correct |
177 ms |
9080 KB |
n = 16 |
35 |
Correct |
194 ms |
9088 KB |
n = 16 |
36 |
Correct |
62 ms |
9088 KB |
n = 15 |
37 |
Correct |
11 ms |
9088 KB |
n = 8 |
38 |
Correct |
141 ms |
9080 KB |
n = 16 |
39 |
Correct |
150 ms |
9080 KB |
n = 16 |
40 |
Correct |
9 ms |
9088 KB |
n = 9 |
41 |
Correct |
151 ms |
9080 KB |
n = 16 |
42 |
Correct |
144 ms |
9180 KB |
n = 16 |
43 |
Correct |
134 ms |
9080 KB |
n = 16 |
44 |
Correct |
11 ms |
9088 KB |
n = 9 |
45 |
Correct |
74 ms |
9080 KB |
n = 15 |
46 |
Correct |
138 ms |
9080 KB |
n = 16 |
47 |
Correct |
147 ms |
9084 KB |
n = 16 |
48 |
Correct |
147 ms |
9088 KB |
n = 16 |
49 |
Incorrect |
123 ms |
9136 KB |
answer is not correct: 1 instead of 0 |
50 |
Halted |
0 ms |
0 KB |
- |