Submission #823951

#	Time	Username	Problem	Language	Result	Execution time	Memory
823951		vnm06	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	52 ms	10596 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;

int n;
long long dp[200000][16];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = s.size();
    int st2=(1<<n);
    for(int i=1; i<st2; i++)
    {
        int br1=0, pos=0;
        for(int j=0; j<n; j++)
        {
            if((1<<j)&i) {br1++; pos=j;}
        }
        if(br1==1) {dp[i][pos]=0; continue;}
        for(int j=0; j<n; j++)
        {
            dp[i][j]=1e18;
            if(!((1<<j)&i)) continue;
            for(int k=0; k<n; k++)
            {
                if(!((1<<k)&i) || k==j) continue;
                long long st=dp[i^(1<<j)][k];
                if(s[j]<t[k]) st+=t[k]-s[j];
                if(st<dp[i][j]) dp[i][j]=st;
               ///cout<<i<<" "<<j<<" "<<k<<" "<<" "<<s[j]<<" "<<t[j]<<" "<<s[k]<<" "<<t[k]<<endl;
            }
        }
    }
    long long mst=1e18;
    for(int i=0; i<n; i++) if(mst>dp[st2-1][i]) mst=dp[st2-1][i];
    return mst;
}

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