oj.uz

Submission #206357

# Submission time Handle Problem Language Result Execution time Memory
206357 2020-03-03T04:17:00 Z TAISA_ Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 81 ms 11256 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1LL<<60;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    assert(n<=16);
    vector<vector<ll>> dp(1<<n,vector<ll>(n,INF));
    for(int i=0;i<n;i++)dp[0][i]=0;
    for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(((i>>j)&1)||i==0){
				for(int k=0;k<n;k++){
					if((i>>k)&1)continue;
					dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+(i==0?0:max(0,t[j]-s[k])));
				}
			}
		}
	}
	ll res=INF;
	for(int i=0;i<n;i++){
		res=min(res,dp[(1<<n)-1][i]);
	}
    return res;
}
/*
4
1 7
4 3
5 8
6 6
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB n = 2
2 Correct 5 ms 256 KB n = 2
3 Correct 5 ms 256 KB n = 2
4 Correct 6 ms 508 KB n = 2
5 Correct 5 ms 256 KB n = 2
6 Correct 5 ms 376 KB n = 2
7 Correct 5 ms 248 KB n = 3
8 Correct 5 ms 376 KB n = 3
9 Correct 5 ms 376 KB n = 3
10 Correct 5 ms 376 KB n = 8
11 Correct 5 ms 376 KB n = 8
12 Correct 5 ms 376 KB n = 8
13 Correct 5 ms 376 KB n = 8
14 Correct 5 ms 376 KB n = 8
15 Correct 5 ms 376 KB n = 8
16 Correct 5 ms 376 KB n = 8
17 Correct 5 ms 376 KB n = 8
18 Correct 5 ms 376 KB n = 8
19 Correct 5 ms 376 KB n = 3
20 Correct 5 ms 376 KB n = 7
21 Correct 5 ms 376 KB n = 8
22 Correct 5 ms 248 KB n = 8
23 Correct 5 ms 376 KB n = 8
24 Correct 5 ms 376 KB n = 8
25 Correct 5 ms 376 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB n = 2
2 Correct 5 ms 256 KB n = 2
3 Correct 5 ms 256 KB n = 2
4 Correct 6 ms 508 KB n = 2
5 Correct 5 ms 256 KB n = 2
6 Correct 5 ms 376 KB n = 2
7 Correct 5 ms 248 KB n = 3
8 Correct 5 ms 376 KB n = 3
9 Correct 5 ms 376 KB n = 3
10 Correct 5 ms 376 KB n = 8
11 Correct 5 ms 376 KB n = 8
12 Correct 5 ms 376 KB n = 8
13 Correct 5 ms 376 KB n = 8
14 Correct 5 ms 376 KB n = 8
15 Correct 5 ms 376 KB n = 8
16 Correct 5 ms 376 KB n = 8
17 Correct 5 ms 376 KB n = 8
18 Correct 5 ms 376 KB n = 8
19 Correct 5 ms 376 KB n = 3
20 Correct 5 ms 376 KB n = 7
21 Correct 5 ms 376 KB n = 8
22 Correct 5 ms 248 KB n = 8
23 Correct 5 ms 376 KB n = 8
24 Correct 5 ms 376 KB n = 8
25 Correct 5 ms 376 KB n = 8
26 Correct 5 ms 376 KB n = 8
27 Correct 5 ms 376 KB n = 8
28 Correct 5 ms 376 KB n = 8
29 Correct 54 ms 11256 KB n = 16
30 Correct 50 ms 11128 KB n = 16
31 Correct 51 ms 11128 KB n = 16
32 Correct 52 ms 11128 KB n = 16
33 Correct 52 ms 11128 KB n = 16
34 Correct 52 ms 11128 KB n = 16
35 Correct 53 ms 11256 KB n = 16
36 Correct 25 ms 5240 KB n = 15
37 Correct 5 ms 376 KB n = 8
38 Correct 53 ms 11128 KB n = 16
39 Correct 56 ms 11256 KB n = 16
40 Correct 5 ms 376 KB n = 9
41 Correct 52 ms 11132 KB n = 16
42 Correct 52 ms 11128 KB n = 16
43 Correct 55 ms 11128 KB n = 16
44 Correct 5 ms 376 KB n = 9
45 Correct 26 ms 5240 KB n = 15
46 Correct 51 ms 11128 KB n = 16
47 Correct 52 ms 11128 KB n = 16
48 Correct 51 ms 11128 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB n = 2
2 Correct 5 ms 256 KB n = 2
3 Correct 5 ms 256 KB n = 2
4 Correct 6 ms 508 KB n = 2
5 Correct 5 ms 256 KB n = 2
6 Correct 5 ms 376 KB n = 2
7 Correct 5 ms 248 KB n = 3
8 Correct 5 ms 376 KB n = 3
9 Correct 5 ms 376 KB n = 3
10 Correct 5 ms 376 KB n = 8
11 Correct 5 ms 376 KB n = 8
12 Correct 5 ms 376 KB n = 8
13 Correct 5 ms 376 KB n = 8
14 Correct 5 ms 376 KB n = 8
15 Correct 5 ms 376 KB n = 8
16 Correct 5 ms 376 KB n = 8
17 Correct 5 ms 376 KB n = 8
18 Correct 5 ms 376 KB n = 8
19 Correct 5 ms 376 KB n = 3
20 Correct 5 ms 376 KB n = 7
21 Correct 5 ms 376 KB n = 8
22 Correct 5 ms 248 KB n = 8
23 Correct 5 ms 376 KB n = 8
24 Correct 5 ms 376 KB n = 8
25 Correct 5 ms 376 KB n = 8
26 Correct 5 ms 376 KB n = 8
27 Correct 5 ms 376 KB n = 8
28 Correct 5 ms 376 KB n = 8
29 Correct 54 ms 11256 KB n = 16
30 Correct 50 ms 11128 KB n = 16
31 Correct 51 ms 11128 KB n = 16
32 Correct 52 ms 11128 KB n = 16
33 Correct 52 ms 11128 KB n = 16
34 Correct 52 ms 11128 KB n = 16
35 Correct 53 ms 11256 KB n = 16
36 Correct 25 ms 5240 KB n = 15
37 Correct 5 ms 376 KB n = 8
38 Correct 53 ms 11128 KB n = 16
39 Correct 56 ms 11256 KB n = 16
40 Correct 5 ms 376 KB n = 9
41 Correct 52 ms 11132 KB n = 16
42 Correct 52 ms 11128 KB n = 16
43 Correct 55 ms 11128 KB n = 16
44 Correct 5 ms 376 KB n = 9
45 Correct 26 ms 5240 KB n = 15
46 Correct 51 ms 11128 KB n = 16
47 Correct 52 ms 11128 KB n = 16
48 Correct 51 ms 11128 KB n = 16
49 Runtime error 81 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -