Submission #568216

#	Time	Username	Problem	Language	Result	Execution time	Memory
568216		definitelynotmee	Roller Coaster Railroad (IOI16_railroad)	C++98	34 / 100	49 ms	11092 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll INFL = (1ll<<62);

ll plan_roller_coaster(vector<int> s, vector<int>t){
    int n =  s.size();
    
    matrix<ll> dp(1<<n,vector<ll>(n,INFL));
    fill(all(dp[0]),0);
    for(int i = 0; i < n; i++)
        dp[1<<i][i] = 0;
        
    for(int i = 0; i < (1<<n); i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(!((1<<k)&i))
                    continue;
                dp[i][k] = min(dp[i][k],dp[i^(1<<k)][j]+max(0,t[j]-s[k])); 
            }
        }
    }

    return *min_element(all(dp[(1<<n)-1]));

}

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