Submission #299401

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

railroad

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

const int N = 16 ;
const long long oo = 1e15 ;

long long dp [(1<<N)][N+1] ;
int mk = 0 ;
int n = 0 ;
int S[N+2], T[N+2] ;

long long go ( int mask, int lst ) {
    if ( mk == mask ) return 0 ;
    auto &rf = dp[mask][lst] ;
    if ( rf!=-1 ) return rf;
    rf = oo ;
    for ( int j = 0 ; j < n ; ++j ) {
        if ( mask & (1<<j) ) continue ;
        int v = 0 ;
        if ( mask ) v = max ( 0, T[lst] - S[j]) ;
        rf = min ( rf, go (mask | (1<<j), j) + v ) ;
    }
    return rf ;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    mk = (1<<n)-1 ;
    for ( int i = 0 ; i < n ; ++i ) S[i] = s[i], T[i] = t[i] ;
    memset ( dp, -1, sizeof dp ) ;
    return go ( 0, 0 );
}

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