Submission #1246808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246808		madamadam3	Roller Coaster Railroad (IOI16_railroad)	C++20	11 / 100	2093 ms	589824 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi =vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
using vb = vector<bool>;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) int(x.size())

const ll INF = 4e18;
int n;
vvpi adj;

ll dfs(int u, vb vis, ll dist, vi order) {
    vis[u] = true; order.push_back(u);
    if (!count(all(vis), false)) {
        return dist;
    }

    ll best = INF;
    for (auto &el : adj[u]) {
        int v = el.second; ll w = el.first;
        if (vis[v]) continue;
        
        best = min(best, dfs(v, vis, dist + w, order));
    }

    return best;
}

ll plan_roller_coaster(vi s, vi t) {
    n = sz(s); adj.assign(n+1, vpi());

    FOR(i, 0, n) {
        adj[n].push_back({0, i});
        FOR(j, 0, n) {
            if (i == j) continue;
            adj[i].push_back({max(0, t[i] - s[j]), j});
        }
    }

    ll ans = dfs(n, vb(n+1, false), 0LL, vi());    
    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: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36