Submission #100030

#	Time	Username	Problem	Language	Result	Execution time	Memory
100030		ShaneOng	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	155 ms	9912 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define INF 10000000000000009ll
using namespace std;
typedef long long ll;
int n;
ll memo[17][(1<<16)+10];
vector<int> a,b;
ll dp(int i, int bitmask){
    if(bitmask==((1<<n)-1)){
        //printf("test\n");
        return memo[i][bitmask]=0ll;
    }
    if(memo[i][bitmask]!=-1ll){
        return memo[i][bitmask];
    }
    //printf("%d %d\n",i,bitmask);
    memo[i][bitmask]=INF;
    for(int x=0;x<n;x++){
        if(((1<<x)&bitmask)==0){
            memo[i][bitmask]=min(memo[i][bitmask],dp(x,bitmask|(1<<x))+max(0ll,(ll)b[i]-a[x]));

        }
    }
    return memo[i][bitmask];
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int) s.size();
    //printf("%d\n",n);
    a=s,b=t;
    for(int x=0;x<n;x++){
        for(int y=0;y<=(1<<n);y++)
            memo[x][y]=-1ll;
    }
    ll ans=INF;
    for(int x=0;x<n;x++)
        ans=min(ans,dp(x,(1<<x)));
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36