Submission #600466

#	Time	Username	Problem	Language	Result	Execution time	Memory
600466		A_D	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	44 ms	9040 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

const int N=140000;
long long dp[N][17];


long long plan_roller_coaster(vector<int> s,vector<int> t){
    int n = (int) s.size();
    for(int i=0;i<n;i++){
        for(int j=1;j<(1<<n);j++){
            dp[j][i]=1e18;
        }
    }
    for(int i=0;i<n;i++){
        dp[(1<<i)][i]=0;
    }
//    cout<<(1&(1<<0))<<"\n";
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if((i&(1<<j))==0)continue;
  //          cout<<"------------------------------------\n";
    //        cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
            for(int k=0;k<n;k++){
                if(((1<<k)&i)!=0){
                    continue;
                }
                long long me=max(t[j]-s[k],(int)0);
      //          cout<<k<<" "<<me<<"\n";
                dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+me);
            }
        }
    }
    long long mn=1e18;
    int lst=(1<<n)-1;
    for(int i=0;i<n;i++){
        mn=min(mn,dp[lst][i]);
    }
    return mn;
}

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