Submission #1203043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203043		onbert	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	551 ms	589824 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

bool cmp(int a, int b) {
    int A = 0, B = 0;
    for (int i=0;i<20;i++) {
        if (a & (1<<i)) A++;
        if (b & (1<<i)) B++;
    }
    return (A < B);
}

long long plan_roller_coaster(std::vector<int32_t> s, std::vector<int32_t> t) {
    int n = s.size(), N = (1<<n);

    int ans1 = 0;
    map<int,int> mp;
    for (int i=0;i<n;i++) {
        mp[s[i]]--;
        mp[t[i]]++;
    }
    int val = 0;
    for (auto [x, y]:mp) {
        val += y;
        if (val < 0) ans1 = 1;
    }

    int dist[N][n];
    for (int i=0;i<N;i++) for (int j=0;j<n;j++) dist[i][j] = INF;
    dist[0][0] = 0;
    vector<int> vals;
    for (int i=0;i<N;i++) vals.push_back(i);
    sort(vals.begin(), vals.end(), cmp);
    for (int i:vals) {
        for (int j=0;j<n;j++) if (i & (1<<j) || i==0) {
            for (int k=0;k<n;k++) if (!(i & (1<<k))) {
                int v = (i | (1<<k)), inc = max(t[j] - s[k], 0);
                if (i==0) inc = 0;
                dist[v][k] = min(dist[i][j] + inc, dist[v][k]);
            }
        }
    }
    int ans = INF;
    for (int i=0;i<n;i++) ans = min(dist[N-1][i], ans);
    if (ans1 == 0) assert(ans == 0);
    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