Submission #610958

#	Time	Username	Problem	Language	Result	Execution time	Memory
610958		PiejanVDC	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	219 ms	524288 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

long long plan_roller_coaster(vector<int>s, vector<int>t) {
    int n = s.size();
    long long v[1<<n][16];
    for(int mask = 1 ; mask < (1<<n) ; mask++) {
        if(__builtin_popcount(mask) == 1) {
            for(int ii = 0 ; ii < 16 ; ii++)
                v[mask][ii] = 1e15;
            v[mask][(int)log2(mask)] = 0;
            continue;
        }
        for(int j = 0 ; j < n ; j++) if(mask & (1 << j)) {
            v[mask][j] = 1e15;
            for(int k = 0 ; k < n ; k++) if(k != j && (mask&(1<<k))) {
                v[mask][j] = min(v[mask][j], v[mask^(1<<j)][k] + max(0, t[k] - s[j]));
            }
        }
    }

    long long ans = LLONG_MAX;
    for(int i = 0 ; i < n ; i++)
        ans = min(ans, v[(1<<n)-1][i]);
    return ans;
}

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