Submission #287533

#	Time	Username	Problem	Language	Result	Execution time	Memory
287533		infinite_iq	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	97 ms	28428 KiB

railroad

#include <bits/stdc++.h>
using namespace std ;
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define C continue 
typedef long long ll ;
typedef vector < int > vi ;
const ll inf = 1e18 ;
#include "railroad.h"
ll n ;
ll in [17] , out [17] ; 
ll dp [(1<<16)+1][17] ;
ll bt ( ll mask , ll last ) {
        if ( __builtin_popcount ( mask ) == n ) return 0ll ;
        ll &ret = dp [mask][last] ;
        if ( ret != -1 ) return ret ;
        ret = inf ;
        for ( ll nxt = 0 ; nxt < n ; nxt ++ ) {
                if ( ( mask & ( 1ll << nxt ) ) ) C ;
                ll cost = max ( 0ll , out [last] - in [nxt] ) ;
                ret = min ( ret , bt ( mask | ( 1 << nxt ) , nxt ) + cost ) ;
        }
        return ret ;
}
ll plan_roller_coaster ( vi s , vi t ) {
        mem ( dp , - 1 ) ;
        n = s.size () ;
        for ( int i = 0 ; i < n ; i ++ ) {
                in  [i] = s [i] ;
                out [i] = t [i] ;
        }
        out [n] = 1ll ;
        return bt ( 0 , n ) ;        
}

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