Submission #598426

#	Time	Username	Problem	Language	Result	Execution time	Memory
598426		Pyishtell	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	49 ms	10584 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) {
    int n = (int) s.size();
    ll way = pow(2,n);
    ll dp[way][n] = {1000000000000000000};
    for(ll i=0; i<way; i++){
        for(ll j=0; j<n; j++){
            if(i/int(pow(2,j))==1 && i%int(pow(2,j))==0) dp[i][j] = 0;
            else if((i/int(pow(2,j)))%2==1){
                ll a = i-pow(2,j);
                for(int k=0; k<n; k++){
                    if((a/int(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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36