Submission #598434

#	Time	Username	Problem	Language	Result	Execution time	Memory
598434		Pyishtell	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	364 ms	8496 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    ll n = (ll) s.size();
    ll way = pow(2,n);
    ll dp[way][n];
    for(int i=0; i<way; i++){
        for(ll j=0; j<n; j++){
            dp[i][j] = 1000000000000000000;
        }
    }
    for(ll i=1; i<way; i++){
        for(ll j=0; j<n; j++){
            if(i==ll(pow(2,j))){
                dp[i][j] = 0;
                continue;
            }
            else if((i/ll(pow(2,j)))%2==1){
                ll a = i-pow(2,j);
                for(ll k=0; k<n; k++){
                    if((a/ll(pow(2,k)))%2==1){
                        dp[i][j] = min(dp[a][k]+max(0,t[j]-s[k]),dp[i][j]);
                    }
                }
            }
        }
    }
    ll ans=dp[way-1][0];
    for(int i=0; i<n; i++){
        ans = min(dp[way-1][i],ans);
    }
    return ans;
}

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