Submission #1188171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188171		anmattroi	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	38 ms	8620 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

template <class T> inline constexpr void cmin(T &x, const T &y) {if (x > y) x = y;}

int64_t f[1<<16][16];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();

    for (int i = 0; i < (1<<n); i++) for (int j = 0; j < n; j++) f[i][j] = LLONG_MAX/2;

    for (int mask = 1; mask < (1<<n); mask++) {
        if (__builtin_popcount(mask) == 1) {
            f[mask][__lg(mask)] = 0;
            continue;
        }
        for (int i = 0; i < n; i++)
        if (mask>>i&1) {
            int x = (mask^(1<<i));
            for (int j = 0; j < n; j++)
            if (x>>j&1) cmin(f[mask][i], f[x][j] + max(0, t[j]-s[i]));
        }
    }

    int64_t ans = LLONG_MAX/2;
    for (int i = 0; i < n; i++) cmin(ans, f[(1<<n)-1][i]);
    return ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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