oj.uz

Submission #64861

# Submission time Handle Problem Language Result Execution time Memory
64861 2018-08-06T00:08:21 Z yogahmad Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 243 ms 13604 KB 
#include "railroad.h"

#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
int n;
long long dep[18][(1<<16)+10];
vector<int>S,T;

long long dp(int now,int mask){
	if(__builtin_popcount(mask)==n)return 0;
	long long&ret=dep[now][mask];
	if(ret!=-1)return ret;
	ret=1e18;
	for(int i=0;i<n;i++){
		if(!(mask&(1<<i))){
			long long cost=0;
			if(T[now]>=S[i])cost=T[now]-S[i];
			int nex=mask|(1<<i);
			ret=min(ret,dp(i,nex)+cost);
		}
	}
	return ret;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n=s.size();
    t.pb(1);
    S=s;
    T=t;
    if(n<=16){
    	reset(dep,-1);
    	return dp(n,0);
	}
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9724 KB n = 2
2 Correct 10 ms 9828 KB n = 2
3 Correct 11 ms 9828 KB n = 2
4 Correct 10 ms 9848 KB n = 2
5 Correct 10 ms 10028 KB n = 2
6 Correct 10 ms 10028 KB n = 2
7 Correct 12 ms 10032 KB n = 3
8 Correct 11 ms 10036 KB n = 3
9 Correct 12 ms 10080 KB n = 3
10 Correct 12 ms 10084 KB n = 8
11 Correct 12 ms 10212 KB n = 8
12 Correct 10 ms 10212 KB n = 8
13 Correct 12 ms 10212 KB n = 8
14 Correct 11 ms 10212 KB n = 8
15 Correct 12 ms 10212 KB n = 8
16 Correct 12 ms 10212 KB n = 8
17 Correct 13 ms 10212 KB n = 8
18 Correct 10 ms 10212 KB n = 8
19 Correct 11 ms 10212 KB n = 3
20 Correct 11 ms 10212 KB n = 7
21 Correct 11 ms 10212 KB n = 8
22 Correct 10 ms 10212 KB n = 8
23 Correct 11 ms 10264 KB n = 8
24 Correct 11 ms 10264 KB n = 8
25 Correct 10 ms 10264 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9724 KB n = 2
2 Correct 10 ms 9828 KB n = 2
3 Correct 11 ms 9828 KB n = 2
4 Correct 10 ms 9848 KB n = 2
5 Correct 10 ms 10028 KB n = 2
6 Correct 10 ms 10028 KB n = 2
7 Correct 12 ms 10032 KB n = 3
8 Correct 11 ms 10036 KB n = 3
9 Correct 12 ms 10080 KB n = 3
10 Correct 12 ms 10084 KB n = 8
11 Correct 12 ms 10212 KB n = 8
12 Correct 10 ms 10212 KB n = 8
13 Correct 12 ms 10212 KB n = 8
14 Correct 11 ms 10212 KB n = 8
15 Correct 12 ms 10212 KB n = 8
16 Correct 12 ms 10212 KB n = 8
17 Correct 13 ms 10212 KB n = 8
18 Correct 10 ms 10212 KB n = 8
19 Correct 11 ms 10212 KB n = 3
20 Correct 11 ms 10212 KB n = 7
21 Correct 11 ms 10212 KB n = 8
22 Correct 10 ms 10212 KB n = 8
23 Correct 11 ms 10264 KB n = 8
24 Correct 11 ms 10264 KB n = 8
25 Correct 10 ms 10264 KB n = 8
26 Correct 11 ms 10264 KB n = 8
27 Correct 11 ms 10264 KB n = 8
28 Correct 11 ms 10264 KB n = 8
29 Correct 172 ms 10264 KB n = 16
30 Correct 172 ms 10264 KB n = 16
31 Correct 173 ms 10264 KB n = 16
32 Correct 199 ms 10264 KB n = 16
33 Correct 180 ms 10320 KB n = 16
34 Correct 176 ms 10324 KB n = 16
35 Correct 148 ms 10324 KB n = 16
36 Correct 112 ms 10324 KB n = 15
37 Correct 10 ms 10324 KB n = 8
38 Correct 159 ms 10324 KB n = 16
39 Correct 193 ms 10324 KB n = 16
40 Correct 10 ms 10324 KB n = 9
41 Correct 243 ms 10352 KB n = 16
42 Correct 191 ms 10356 KB n = 16
43 Correct 183 ms 10356 KB n = 16
44 Correct 11 ms 10356 KB n = 9
45 Correct 58 ms 10356 KB n = 15
46 Correct 180 ms 10356 KB n = 16
47 Correct 151 ms 10356 KB n = 16
48 Correct 144 ms 10356 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10356 KB n = 199999
2 Incorrect 89 ms 13604 KB answer is not correct: 0 instead of 1
3 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9724 KB n = 2
2 Correct 10 ms 9828 KB n = 2
3 Correct 11 ms 9828 KB n = 2
4 Correct 10 ms 9848 KB n = 2
5 Correct 10 ms 10028 KB n = 2
6 Correct 10 ms 10028 KB n = 2
7 Correct 12 ms 10032 KB n = 3
8 Correct 11 ms 10036 KB n = 3
9 Correct 12 ms 10080 KB n = 3
10 Correct 12 ms 10084 KB n = 8
11 Correct 12 ms 10212 KB n = 8
12 Correct 10 ms 10212 KB n = 8
13 Correct 12 ms 10212 KB n = 8
14 Correct 11 ms 10212 KB n = 8
15 Correct 12 ms 10212 KB n = 8
16 Correct 12 ms 10212 KB n = 8
17 Correct 13 ms 10212 KB n = 8
18 Correct 10 ms 10212 KB n = 8
19 Correct 11 ms 10212 KB n = 3
20 Correct 11 ms 10212 KB n = 7
21 Correct 11 ms 10212 KB n = 8
22 Correct 10 ms 10212 KB n = 8
23 Correct 11 ms 10264 KB n = 8
24 Correct 11 ms 10264 KB n = 8
25 Correct 10 ms 10264 KB n = 8
26 Correct 11 ms 10264 KB n = 8
27 Correct 11 ms 10264 KB n = 8
28 Correct 11 ms 10264 KB n = 8
29 Correct 172 ms 10264 KB n = 16
30 Correct 172 ms 10264 KB n = 16
31 Correct 173 ms 10264 KB n = 16
32 Correct 199 ms 10264 KB n = 16
33 Correct 180 ms 10320 KB n = 16
34 Correct 176 ms 10324 KB n = 16
35 Correct 148 ms 10324 KB n = 16
36 Correct 112 ms 10324 KB n = 15
37 Correct 10 ms 10324 KB n = 8
38 Correct 159 ms 10324 KB n = 16
39 Correct 193 ms 10324 KB n = 16
40 Correct 10 ms 10324 KB n = 9
41 Correct 243 ms 10352 KB n = 16
42 Correct 191 ms 10356 KB n = 16
43 Correct 183 ms 10356 KB n = 16
44 Correct 11 ms 10356 KB n = 9
45 Correct 58 ms 10356 KB n = 15
46 Correct 180 ms 10356 KB n = 16
47 Correct 151 ms 10356 KB n = 16
48 Correct 144 ms 10356 KB n = 16
49 Correct 87 ms 10356 KB n = 199999
50 Incorrect 89 ms 13604 KB answer is not correct: 0 instead of 1
51 Halted 0 ms 0 KB -