Submission #1265571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265571		gustavo_d	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	25 ms	8620 KiB

railroad

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

typedef long long ll;

const int MAXN = 16;

ll dp[MAXN][1 << MAXN];

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();

    for (int i=0; i<n; i++) {
        for (int m=0; m<(1 << n); m++) dp[i][m] = 1e18;
    }

    for (int m=1; m<(1 << n); m++) {
        vector<int> v;
        for (int i=0; i<n; i++) {
            if (((1 << i) & m) != 0) v.push_back(i);
        }
        // for (int i : v) cout << i << ' ';
        // cout << ':';
        if (v.size() == 1) {
            dp[v[0]][m] = 0;
        }
        for (int i : v) {
            for (int j : v) {
                if (i == j) continue;
                assert ((m-(1<<i)) == (m^(1<<i)));
                // cout << j << "->" << i << '=' << t[j] << ' ' << s[i] << ' ' << t[j]-s[i] << endl;
                dp[i][m] = min(
                    dp[i][m],
                    dp[j][m ^ (1 << i)] + max(0, t[j]-s[i])
                );
            }

            // cout << dp[i][m] << ' ';
        }
        // cout << endl;
    }
    ll ans = 1e18;
    for (int i=0; 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