Submission #1137445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137445		gyg	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	141 ms	7256 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
#define ub upper_bound 
const int N = 18, INF = 1e18;

int n;
arr<int, N> s, t;

int wt(int i) { return 1 << (i - 1); }
bool on(int x, int i) { return x & wt(i); }
vec<int> in(int x) {
    vec<int> ans;
    for (int i = 1; i <= n; i++)
        if (on(x, i)) ans.push_back(i);
    return ans;
}

arr<arr<int, 1 << N>, N> dp;
void dp_cmp() {
    for (int st = 1; st < (1 << n); st++) {
        if (in(st).size() == 1) continue;
        for (int i : in(st)) {
            dp[i][st] = INF;
            int nw_st = st ^ wt(i);
            for (int j : in(st)) {
                if (j == i) continue;
                dp[i][st] = min(dp[i][st], dp[j][nw_st] + max(t[j] - s[i], 0ll));
            }
        }
    }
}

int plan_roller_coaster(vec<signed> _s, vec<signed> _t) {
    n = _s.size();
    for (int i = 1; i <= n; i++) s[i] = _s[i - 1], t[i] = _t[i - 1];
    dp_cmp();
    
    int ans = INF;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << n) - 1]);
    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