oj.uz

Submission #239263

# Submission time Handle Problem Language Result Execution time Memory
239263 2020-06-15T04:44:49 Z urd05 Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 97 ms 30584 KB 
#include <bits/stdc++.h>
using namespace std;

long long dp[16][65536]; //recent,visited.
int need[200000];
int sp[200000];
int n;

long long ans(int rec,int bit) {
    if (dp[rec][bit]!=-1) {
        return dp[rec][bit];
    }
    if (bit==(1<<rec)) {
        dp[rec][bit]=0;
        return dp[rec][bit];
    }
    long long ret=1e15;
    for(int i=0;i<n;i++) {
        if (i!=rec&&((bit>>i)&1)) {
            ret=min(ret,ans(i,bit-(1<<rec))+max(0,sp[i]-need[rec]));
        }
    }
    dp[rec][bit]=ret;
    return ret;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    for(int i=0;i<n;i++) {
        need[i]=s[i];
        sp[i]=t[i];
    }
    memset(dp,-1,sizeof(dp));
    long long ret=1e15;
    for(int i=0;i<n;i++) {
        ret=min(ret,ans(i,(1<<n)-1));
    }
    return ret;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB n = 2
2 Correct 9 ms 8448 KB n = 2
3 Correct 10 ms 8448 KB n = 2
4 Correct 9 ms 8576 KB n = 2
5 Correct 9 ms 8576 KB n = 2
6 Correct 9 ms 8576 KB n = 2
7 Correct 8 ms 8448 KB n = 3
8 Correct 9 ms 8576 KB n = 3
9 Correct 9 ms 8576 KB n = 3
10 Correct 9 ms 8496 KB n = 8
11 Correct 9 ms 8576 KB n = 8
12 Correct 9 ms 8576 KB n = 8
13 Correct 9 ms 8576 KB n = 8
14 Correct 8 ms 8576 KB n = 8
15 Correct 9 ms 8576 KB n = 8
16 Correct 9 ms 8576 KB n = 8
17 Correct 9 ms 8576 KB n = 8
18 Correct 9 ms 8576 KB n = 8
19 Correct 9 ms 8576 KB n = 3
20 Correct 9 ms 8576 KB n = 7
21 Correct 9 ms 8576 KB n = 8
22 Correct 8 ms 8576 KB n = 8
23 Correct 9 ms 8576 KB n = 8
24 Correct 9 ms 8576 KB n = 8
25 Correct 9 ms 8576 KB n = 8
26 Correct 9 ms 8576 KB n = 8
27 Correct 10 ms 8576 KB n = 8
28 Correct 10 ms 8576 KB n = 8
29 Correct 62 ms 8576 KB n = 16
30 Correct 63 ms 8576 KB n = 16
31 Correct 67 ms 8696 KB n = 16
32 Correct 60 ms 8576 KB n = 16
33 Correct 70 ms 8576 KB n = 16
34 Correct 57 ms 8576 KB n = 16
35 Correct 59 ms 8576 KB n = 16
36 Correct 28 ms 8576 KB n = 15
37 Correct 9 ms 8576 KB n = 8
38 Correct 62 ms 8576 KB n = 16
39 Correct 62 ms 8576 KB n = 16
40 Correct 9 ms 8576 KB n = 9
41 Correct 62 ms 8576 KB n = 16
42 Correct 56 ms 8576 KB n = 16
43 Correct 60 ms 8576 KB n = 16
44 Correct 9 ms 8576 KB n = 9
45 Correct 27 ms 8576 KB n = 15
46 Correct 56 ms 8576 KB n = 16
47 Correct 55 ms 8576 KB n = 16
48 Correct 54 ms 8576 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 30584 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 8 ms 8576 KB n = 2
2 Correct 9 ms 8448 KB n = 2
3 Correct 10 ms 8448 KB n = 2
4 Correct 9 ms 8576 KB n = 2
5 Correct 9 ms 8576 KB n = 2
6 Correct 9 ms 8576 KB n = 2
7 Correct 8 ms 8448 KB n = 3
8 Correct 9 ms 8576 KB n = 3
9 Correct 9 ms 8576 KB n = 3
10 Correct 9 ms 8496 KB n = 8
11 Correct 9 ms 8576 KB n = 8
12 Correct 9 ms 8576 KB n = 8
13 Correct 9 ms 8576 KB n = 8
14 Correct 8 ms 8576 KB n = 8
15 Correct 9 ms 8576 KB n = 8
16 Correct 9 ms 8576 KB n = 8
17 Correct 9 ms 8576 KB n = 8
18 Correct 9 ms 8576 KB n = 8
19 Correct 9 ms 8576 KB n = 3
20 Correct 9 ms 8576 KB n = 7
21 Correct 9 ms 8576 KB n = 8
22 Correct 8 ms 8576 KB n = 8
23 Correct 9 ms 8576 KB n = 8
24 Correct 9 ms 8576 KB n = 8
25 Correct 9 ms 8576 KB n = 8
26 Correct 9 ms 8576 KB n = 8
27 Correct 10 ms 8576 KB n = 8
28 Correct 10 ms 8576 KB n = 8
29 Correct 62 ms 8576 KB n = 16
30 Correct 63 ms 8576 KB n = 16
31 Correct 67 ms 8696 KB n = 16
32 Correct 60 ms 8576 KB n = 16
33 Correct 70 ms 8576 KB n = 16
34 Correct 57 ms 8576 KB n = 16
35 Correct 59 ms 8576 KB n = 16
36 Correct 28 ms 8576 KB n = 15
37 Correct 9 ms 8576 KB n = 8
38 Correct 62 ms 8576 KB n = 16
39 Correct 62 ms 8576 KB n = 16
40 Correct 9 ms 8576 KB n = 9
41 Correct 62 ms 8576 KB n = 16
42 Correct 56 ms 8576 KB n = 16
43 Correct 60 ms 8576 KB n = 16
44 Correct 9 ms 8576 KB n = 9
45 Correct 27 ms 8576 KB n = 15
46 Correct 56 ms 8576 KB n = 16
47 Correct 55 ms 8576 KB n = 16
48 Correct 54 ms 8576 KB n = 16
49 Runtime error 97 ms 30584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -