oj.uz

Submission #99996

# Submission time Handle Problem Language Result Execution time Memory
99996 2019-03-09T06:15:58 Z errorgorn Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 191 ms 8696 KB 
#include "railroad.h"
#include <cstring>
#include <cstdio>
using namespace std;
vector<int> gs,gt;
long long memo[16][65539];
int log2(int i){
    int ans=0;
    if (i>=256) ans+=8,i>>=8;
    if (i>=16) ans+=4,i>>=4;
    if (i>=4) ans+=2,i>>=2;
    if (i>=2) ans+=1,i>>=1;
    return ans;
}
int f(int i){
    if (i<0) return 0;
    return i;
}
long long tsp(int i,int bitmask){
    if (bitmask==0) return 0;
    else if (memo[i][bitmask]!=-1) return memo[i][bitmask];
    long long ans=1123456789012345678;
    int c_bitmask=bitmask,temp,log_temp;
    while (c_bitmask!=0){
        temp=c_bitmask&-c_bitmask;
        c_bitmask-=temp;
        log_temp=log2(temp);
        ans=min(ans,tsp(log_temp,bitmask^temp)+ f(gt[i]-gs[log_temp]) );
    }
    return memo[i][bitmask]=ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    gs=s,gt=t;
    int n = (int) s.size();
    if (n>16){
        for (int x=0;x<n;x++){
            if (s[x]==0 || t[x]==0) return 1;
        }
        return 0;
    }
    long long ans=1123456789012345678;
    memset(memo,-1,sizeof(memo));
    for (int x=0;x<n;x++){
        ans=min(ans,tsp(x,((1<<n)-1)^(1<<x) ));
    }
    /*for (int x=0;x<n;x++){
        for (int y=0;y<(1<<n);y++){
            printf("%lld ", memo[x][y]);
        }
        printf("\n");
    }*/
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8576 KB n = 2
2 Correct 9 ms 8576 KB n = 2
3 Correct 9 ms 8576 KB n = 2
4 Correct 9 ms 8576 KB n = 2
5 Correct 8 ms 8576 KB n = 2
6 Correct 8 ms 8448 KB n = 2
7 Correct 10 ms 8448 KB n = 3
8 Correct 10 ms 8448 KB n = 3
9 Correct 8 ms 8448 KB n = 3
10 Correct 11 ms 8576 KB n = 8
11 Correct 9 ms 8448 KB n = 8
12 Correct 10 ms 8448 KB n = 8
13 Correct 9 ms 8576 KB n = 8
14 Correct 9 ms 8448 KB n = 8
15 Correct 10 ms 8576 KB n = 8
16 Correct 10 ms 8576 KB n = 8
17 Correct 10 ms 8576 KB n = 8
18 Correct 10 ms 8576 KB n = 8
19 Correct 9 ms 8576 KB n = 3
20 Correct 8 ms 8448 KB n = 7
21 Correct 9 ms 8448 KB n = 8
22 Correct 9 ms 8576 KB n = 8
23 Correct 9 ms 8576 KB n = 8
24 Correct 12 ms 8576 KB n = 8
25 Correct 12 ms 8576 KB n = 8
26 Correct 12 ms 8576 KB n = 8
27 Correct 9 ms 8576 KB n = 8
28 Correct 10 ms 8576 KB n = 8
29 Correct 103 ms 8568 KB n = 16
30 Correct 116 ms 8696 KB n = 16
31 Correct 191 ms 8568 KB n = 16
32 Correct 143 ms 8576 KB n = 16
33 Correct 99 ms 8576 KB n = 16
34 Correct 94 ms 8576 KB n = 16
35 Correct 83 ms 8588 KB n = 16
36 Correct 36 ms 8552 KB n = 15
37 Correct 9 ms 8448 KB n = 8
38 Correct 94 ms 8448 KB n = 16
39 Correct 110 ms 8552 KB n = 16
40 Correct 10 ms 8672 KB n = 9
41 Correct 104 ms 8448 KB n = 16
42 Correct 111 ms 8576 KB n = 16
43 Correct 78 ms 8552 KB n = 16
44 Correct 8 ms 8448 KB n = 9
45 Correct 41 ms 8548 KB n = 15
46 Correct 102 ms 8576 KB n = 16
47 Correct 127 ms 8448 KB n = 16
48 Correct 87 ms 8552 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5000 KB n = 199999
2 Incorrect 88 ms 5012 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 9 ms 8576 KB n = 2
2 Correct 9 ms 8576 KB n = 2
3 Correct 9 ms 8576 KB n = 2
4 Correct 9 ms 8576 KB n = 2
5 Correct 8 ms 8576 KB n = 2
6 Correct 8 ms 8448 KB n = 2
7 Correct 10 ms 8448 KB n = 3
8 Correct 10 ms 8448 KB n = 3
9 Correct 8 ms 8448 KB n = 3
10 Correct 11 ms 8576 KB n = 8
11 Correct 9 ms 8448 KB n = 8
12 Correct 10 ms 8448 KB n = 8
13 Correct 9 ms 8576 KB n = 8
14 Correct 9 ms 8448 KB n = 8
15 Correct 10 ms 8576 KB n = 8
16 Correct 10 ms 8576 KB n = 8
17 Correct 10 ms 8576 KB n = 8
18 Correct 10 ms 8576 KB n = 8
19 Correct 9 ms 8576 KB n = 3
20 Correct 8 ms 8448 KB n = 7
21 Correct 9 ms 8448 KB n = 8
22 Correct 9 ms 8576 KB n = 8
23 Correct 9 ms 8576 KB n = 8
24 Correct 12 ms 8576 KB n = 8
25 Correct 12 ms 8576 KB n = 8
26 Correct 12 ms 8576 KB n = 8
27 Correct 9 ms 8576 KB n = 8
28 Correct 10 ms 8576 KB n = 8
29 Correct 103 ms 8568 KB n = 16
30 Correct 116 ms 8696 KB n = 16
31 Correct 191 ms 8568 KB n = 16
32 Correct 143 ms 8576 KB n = 16
33 Correct 99 ms 8576 KB n = 16
34 Correct 94 ms 8576 KB n = 16
35 Correct 83 ms 8588 KB n = 16
36 Correct 36 ms 8552 KB n = 15
37 Correct 9 ms 8448 KB n = 8
38 Correct 94 ms 8448 KB n = 16
39 Correct 110 ms 8552 KB n = 16
40 Correct 10 ms 8672 KB n = 9
41 Correct 104 ms 8448 KB n = 16
42 Correct 111 ms 8576 KB n = 16
43 Correct 78 ms 8552 KB n = 16
44 Correct 8 ms 8448 KB n = 9
45 Correct 41 ms 8548 KB n = 15
46 Correct 102 ms 8576 KB n = 16
47 Correct 127 ms 8448 KB n = 16
48 Correct 87 ms 8552 KB n = 16
49 Correct 99 ms 5000 KB n = 199999
50 Incorrect 88 ms 5012 KB answer is not correct: 0 instead of 1
51 Halted 0 ms 0 KB -