Submission #54022

#	Time	Username	Problem	Language	Result	Execution time	Memory
54022		Alexa2001	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	86 ms	9428 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;
const int Nmax = 17;

int n, start[Nmax], finish[Nmax];
ll dp[1<<Nmax][Nmax];

ll solve1(vector<int> &start, vector<int> &finish)
{
    int i, j, k;

    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            dp[i][j] = inf;

    for(i=0; i<n; ++i) dp[1<<i][i] = 0;

    for(i=1; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            if(i&(1<<j))
                for(k=0; k<n; ++k)
                    if(!(i&(1<<k)))
                        dp[i^(1<<k)][k] = min(dp[i^(1<<k)][k], dp[i][j] + max(0, finish[j] - start[k]));

    ll ans = inf;
    for(j=0; j<n; ++j) ans = min(ans, dp[i-1][j]);
    return ans;
}

ll plan_roller_coaster(vector<int> s, vector<int> t)
{
    n = s.size();
    int i;
    for(i=1; i<=n; ++i) start[i] = s[i-1], finish[i] = t[i-1];

    if(n <= 16) return solve1(s, t);

    return 0;
}

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