Submission #99996

#	Time	Username	Problem	Language	Result	Execution time	Memory
99996		errorgorn	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	191 ms	8696 KiB

railroad

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36