Submission #206004

#	Time	Username	Problem	Language	Result	Execution time	Memory
206004		oko	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	125 ms	51800 KiB

railroad

#include "railroad.h"
#include <cstdio>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
long long n,dp[(1<<17)+555][20];
vector<int>en,ex;
long long f(int mask,int last)
{
    if(mask==(1<<n)-1)return 0;
    if(dp[mask][last]!=-1)return dp[mask][last];
    long long ans=1e18;
    for(int i=0;i<n;i++)
    {
        if((mask&(1<<i))==0)
        {
            long long dis=max(0,ex[last]-en[i]);
            ans=min(ans,dis+f((mask|(1<<i)),i));
        }
    }
    return dp[mask][last]=ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
    memset(dp,-1,sizeof dp);
    n=s.size();
    en=s;
    ex=t;
    en.insert(en.begin(),0);
    ex.insert(ex.begin(),1);
    n++;
    long long mn=1e18;
    return f(1,0);
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:32:15: warning: unused variable 'mn' [-Wunused-variable]
     long long mn=1e18;
               ^~

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