Submission #352662

#	Time	Username	Problem	Language	Result	Execution time	Memory
352662		juggernaut	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	94 ms	30172 KiB

railroad

#include"railroad.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
vector<ll>s,t;
int n;
ll inf=9e14,dp[16][65536];
ll rec(int v,int mask){
    if(dp[v][mask]!=-1)return dp[v][mask];
    if((1<<v)==mask)return dp[v][mask]=0ll;
    dp[v][mask]=inf;
    for(int i=0;i<n;i++)if((mask>>i&1)&&i!=v)
        dp[v][mask]=min(dp[v][mask],max(0ll,t[v]-s[i])+rec(i,mask^(1<<v)));
    return dp[v][mask];
}
ll plan_roller_coaster(vector<int>S,vector<int>T){
    for(int to:S)s.push_back(to*1ll);
    for(int to:T)t.push_back(to*1ll);
    n=s.size();
    for(int i=0;i<16;i++)
        for(int j=0;j<65536;j++)dp[i][j]=-1;
    ll res=inf;
    for(int i=0;i<n;i++)res=min(res,rec(i,(1<<n)-1));
    return res;
}

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