Submission #221186

#	Time	Username	Problem	Language	Result	Execution time	Memory
221186		emil_physmath	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	78 ms	7296 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
using uint = unsigned int;
using llong = long long;
const int maxN = 16;

llong dp[maxN + 1][1 << maxN];

inline bool IsSet(uint a, int i) { return a & (1 << i); }
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = s.size();
    if (n > maxN)
        return -1;
    for (uint mask = 1; mask < (1 << n); ++mask)
        for (int i = 0; i < n; ++i)
        {
            if (!IsSet(mask, i)) continue;
            uint bit = (1U << i);
            uint prev = mask ^ bit;
            if (prev == 0)
            {
                dp[i][mask] = 0;
                // cerr << "dp[" << i << "][" << bitset<4>(mask) << "] = " << dp[i][mask] << '\n';
                continue;
            }
            dp[i][mask] = maxN * 1000'000'000LL;
            for (int j = 0; j < n; ++j)
                if (IsSet(prev, j))
                    dp[i][mask] = min(dp[i][mask], dp[j][prev] + max(t[j] - s[i], 0));
            // cerr << "dp[" << i << "][" << bitset<4>(mask) << "] = " << dp[i][mask] << '\n';
        }
    llong ans = maxN * 1000'000'000LL;
    for (int i = 0; i < n; ++i)
        ans = min(dp[i][(1 << n) - 1], ans);
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:17:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (uint mask = 1; mask < (1 << n); ++mask)
                         ~~~~~^~~~~~~~~~

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