#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 200
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 4e18;
const ld pai=acos(-1);
#include "railroad.h"
ll n ;
ll dp[(1<<17)+9][19];
ll l[19],r[19];
ll calc(ll x , ll y ){
if ( x<=y)return 0;
return x-y;
}
ll bt(int mask,int last){
if ( mask == (1<<(n+1)) -1 ) return 0;
ll &ret=dp[mask][last];
if( ret != -1) return ret;
ret = inf;
for(int i =1 ;i <=n; i++){
if ( (mask&(1<<i) ) == 0 ){
ret = min ( ret ,bt ( mask|(1<<i) , i ) + calc(r[last],l[i] ) );
}
}
return ret;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = (int) s.size();
mem(dp,-1);
r [0] = 1;
for(int i = 0 ;i < n ;i ++ ) {
l[i+1]=s[i];
r[i+1]=t[i];
}
return bt(1,0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19832 KB |
n = 2 |
2 |
Correct |
15 ms |
19832 KB |
n = 2 |
3 |
Correct |
16 ms |
19832 KB |
n = 2 |
4 |
Correct |
17 ms |
19832 KB |
n = 2 |
5 |
Correct |
16 ms |
19832 KB |
n = 2 |
6 |
Correct |
17 ms |
19832 KB |
n = 2 |
7 |
Correct |
16 ms |
19832 KB |
n = 3 |
8 |
Correct |
16 ms |
19832 KB |
n = 3 |
9 |
Correct |
16 ms |
19832 KB |
n = 3 |
10 |
Correct |
16 ms |
19832 KB |
n = 8 |
11 |
Correct |
16 ms |
19832 KB |
n = 8 |
12 |
Correct |
16 ms |
19832 KB |
n = 8 |
13 |
Correct |
16 ms |
19832 KB |
n = 8 |
14 |
Correct |
16 ms |
19832 KB |
n = 8 |
15 |
Correct |
16 ms |
19832 KB |
n = 8 |
16 |
Correct |
17 ms |
19832 KB |
n = 8 |
17 |
Correct |
16 ms |
19832 KB |
n = 8 |
18 |
Correct |
16 ms |
19832 KB |
n = 8 |
19 |
Correct |
16 ms |
19832 KB |
n = 3 |
20 |
Correct |
16 ms |
19832 KB |
n = 7 |
21 |
Correct |
19 ms |
19832 KB |
n = 8 |
22 |
Correct |
16 ms |
19832 KB |
n = 8 |
23 |
Correct |
16 ms |
19832 KB |
n = 8 |
24 |
Correct |
15 ms |
19832 KB |
n = 8 |
25 |
Correct |
15 ms |
19832 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19832 KB |
n = 2 |
2 |
Correct |
15 ms |
19832 KB |
n = 2 |
3 |
Correct |
16 ms |
19832 KB |
n = 2 |
4 |
Correct |
17 ms |
19832 KB |
n = 2 |
5 |
Correct |
16 ms |
19832 KB |
n = 2 |
6 |
Correct |
17 ms |
19832 KB |
n = 2 |
7 |
Correct |
16 ms |
19832 KB |
n = 3 |
8 |
Correct |
16 ms |
19832 KB |
n = 3 |
9 |
Correct |
16 ms |
19832 KB |
n = 3 |
10 |
Correct |
16 ms |
19832 KB |
n = 8 |
11 |
Correct |
16 ms |
19832 KB |
n = 8 |
12 |
Correct |
16 ms |
19832 KB |
n = 8 |
13 |
Correct |
16 ms |
19832 KB |
n = 8 |
14 |
Correct |
16 ms |
19832 KB |
n = 8 |
15 |
Correct |
16 ms |
19832 KB |
n = 8 |
16 |
Correct |
17 ms |
19832 KB |
n = 8 |
17 |
Correct |
16 ms |
19832 KB |
n = 8 |
18 |
Correct |
16 ms |
19832 KB |
n = 8 |
19 |
Correct |
16 ms |
19832 KB |
n = 3 |
20 |
Correct |
16 ms |
19832 KB |
n = 7 |
21 |
Correct |
19 ms |
19832 KB |
n = 8 |
22 |
Correct |
16 ms |
19832 KB |
n = 8 |
23 |
Correct |
16 ms |
19832 KB |
n = 8 |
24 |
Correct |
15 ms |
19832 KB |
n = 8 |
25 |
Correct |
15 ms |
19832 KB |
n = 8 |
26 |
Correct |
16 ms |
19832 KB |
n = 8 |
27 |
Correct |
15 ms |
19832 KB |
n = 8 |
28 |
Correct |
16 ms |
19832 KB |
n = 8 |
29 |
Correct |
89 ms |
19960 KB |
n = 16 |
30 |
Correct |
91 ms |
19832 KB |
n = 16 |
31 |
Correct |
86 ms |
19836 KB |
n = 16 |
32 |
Correct |
86 ms |
19832 KB |
n = 16 |
33 |
Correct |
88 ms |
19960 KB |
n = 16 |
34 |
Correct |
90 ms |
19784 KB |
n = 16 |
35 |
Correct |
90 ms |
19832 KB |
n = 16 |
36 |
Correct |
49 ms |
19832 KB |
n = 15 |
37 |
Correct |
16 ms |
19832 KB |
n = 8 |
38 |
Correct |
91 ms |
19832 KB |
n = 16 |
39 |
Correct |
98 ms |
19832 KB |
n = 16 |
40 |
Correct |
16 ms |
19832 KB |
n = 9 |
41 |
Correct |
89 ms |
19828 KB |
n = 16 |
42 |
Correct |
86 ms |
19832 KB |
n = 16 |
43 |
Correct |
99 ms |
19832 KB |
n = 16 |
44 |
Correct |
16 ms |
19832 KB |
n = 9 |
45 |
Correct |
46 ms |
19832 KB |
n = 15 |
46 |
Correct |
93 ms |
19832 KB |
n = 16 |
47 |
Correct |
90 ms |
19860 KB |
n = 16 |
48 |
Correct |
90 ms |
19832 KB |
n = 16 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
92 ms |
26872 KB |
answer is not correct: 1 instead of 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
19832 KB |
n = 2 |
2 |
Correct |
15 ms |
19832 KB |
n = 2 |
3 |
Correct |
16 ms |
19832 KB |
n = 2 |
4 |
Correct |
17 ms |
19832 KB |
n = 2 |
5 |
Correct |
16 ms |
19832 KB |
n = 2 |
6 |
Correct |
17 ms |
19832 KB |
n = 2 |
7 |
Correct |
16 ms |
19832 KB |
n = 3 |
8 |
Correct |
16 ms |
19832 KB |
n = 3 |
9 |
Correct |
16 ms |
19832 KB |
n = 3 |
10 |
Correct |
16 ms |
19832 KB |
n = 8 |
11 |
Correct |
16 ms |
19832 KB |
n = 8 |
12 |
Correct |
16 ms |
19832 KB |
n = 8 |
13 |
Correct |
16 ms |
19832 KB |
n = 8 |
14 |
Correct |
16 ms |
19832 KB |
n = 8 |
15 |
Correct |
16 ms |
19832 KB |
n = 8 |
16 |
Correct |
17 ms |
19832 KB |
n = 8 |
17 |
Correct |
16 ms |
19832 KB |
n = 8 |
18 |
Correct |
16 ms |
19832 KB |
n = 8 |
19 |
Correct |
16 ms |
19832 KB |
n = 3 |
20 |
Correct |
16 ms |
19832 KB |
n = 7 |
21 |
Correct |
19 ms |
19832 KB |
n = 8 |
22 |
Correct |
16 ms |
19832 KB |
n = 8 |
23 |
Correct |
16 ms |
19832 KB |
n = 8 |
24 |
Correct |
15 ms |
19832 KB |
n = 8 |
25 |
Correct |
15 ms |
19832 KB |
n = 8 |
26 |
Correct |
16 ms |
19832 KB |
n = 8 |
27 |
Correct |
15 ms |
19832 KB |
n = 8 |
28 |
Correct |
16 ms |
19832 KB |
n = 8 |
29 |
Correct |
89 ms |
19960 KB |
n = 16 |
30 |
Correct |
91 ms |
19832 KB |
n = 16 |
31 |
Correct |
86 ms |
19836 KB |
n = 16 |
32 |
Correct |
86 ms |
19832 KB |
n = 16 |
33 |
Correct |
88 ms |
19960 KB |
n = 16 |
34 |
Correct |
90 ms |
19784 KB |
n = 16 |
35 |
Correct |
90 ms |
19832 KB |
n = 16 |
36 |
Correct |
49 ms |
19832 KB |
n = 15 |
37 |
Correct |
16 ms |
19832 KB |
n = 8 |
38 |
Correct |
91 ms |
19832 KB |
n = 16 |
39 |
Correct |
98 ms |
19832 KB |
n = 16 |
40 |
Correct |
16 ms |
19832 KB |
n = 9 |
41 |
Correct |
89 ms |
19828 KB |
n = 16 |
42 |
Correct |
86 ms |
19832 KB |
n = 16 |
43 |
Correct |
99 ms |
19832 KB |
n = 16 |
44 |
Correct |
16 ms |
19832 KB |
n = 9 |
45 |
Correct |
46 ms |
19832 KB |
n = 15 |
46 |
Correct |
93 ms |
19832 KB |
n = 16 |
47 |
Correct |
90 ms |
19860 KB |
n = 16 |
48 |
Correct |
90 ms |
19832 KB |
n = 16 |
49 |
Incorrect |
92 ms |
26872 KB |
answer is not correct: 1 instead of 0 |
50 |
Halted |
0 ms |
0 KB |
- |