Submission #72982

#	Time	Username	Problem	Language	Result	Execution time	Memory
72982		MKopchev	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	141 ms	11020 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
const int nmax=16;
int n;
long long dp[1<<nmax][nmax];
vector<int> s,t;
long long rec(int state/*1->active, 0->used*/,int last)
{
    if(state==0)return 0;
    if(dp[state][last]!=-1)return dp[state][last];
    long long ret=1e18;
    for(int i=0;i<n;i++)
        if((state&(1<<i)))
        {
            if(t[last]<=s[i])ret=min(ret,rec(state-(1<<i),i));
            else ret=min(ret,rec(state-(1<<i),i)+t[last]-s[i]);
        }
    dp[state][last]=ret;
    return ret;
}
long long plan_roller_coaster(vector<int> S, vector<int> T)
{
    n=S.size();
    assert(n<=nmax);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)s.push_back(S[i]),t.push_back(T[i]);
    long long ans=1e18;
    for(int i=0;i<n;i++)
        ans=min(ans,rec((1<<n)-1-(1<<i),i));
    return ans;
}
/*
int main()
{
    cout<<plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6})<<endl;
}
*/

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