Submission #108214

#	Time	Username	Problem	Language	Result	Execution time	Memory
108214		tictaccat	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	142 ms	11256 KiB

railroad

#include "railroad.h"

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

const ll INF = 1e18;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {

    int n = (int) s.size();

    vector<vector<ll>> dp((1 << n), vector<ll>(n+1, INF));

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

    ll low = INF;

    for (int i = 2; i <= n; i++) {
        for (int bits = 0; bits < (1 << n); bits++) {
            if (__builtin_popcount(bits) != i) continue;
            for (int j = 0; j < n; j++) {
                if (!(bits & (1<<j))) continue;
                for (int k = 0; k < n; k++) {
                    if (k == j || !(bits&(1<<k))) continue;
                    dp[bits][j] = min(dp[bits][j], dp[bits^(1<<j)][k] + max(0,t[k]-s[j]));
                }
                if (i == n) low = min(low,dp[bits][j]);
            }
        }
    }

    return low;
}

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