# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1208760 | Quentolosse | Roller Coaster Railroad (IOI16_railroad) | C++20 | 612 ms | 167892 KiB |
#include "railroad.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
int n = (int) s.size();
int a = 1 << n;
vector<vector<vector<int>>> dp(n+2, vector<vector<int>> (n+1, vector<int>(a+1, 1e18)));
dp[0][n][0] = 0;
t.push_back(1);
for (int pos = 0; pos < n; pos++)
{
for (int avant = 0; avant <= n; avant++)
{
for (int mask = 0; mask < a; mask++)
{
if (!((mask >> avant) & 1) && avant != n) continue;
for (int prochain = 0; prochain < n; prochain++)
{
if ((mask >> prochain) & 1) continue;
int new_mask = mask | (1 << prochain);
dp[pos+1][prochain][new_mask] = min(dp[pos+1][prochain][new_mask], dp[pos][avant][mask] + max(t[avant] - s[prochain], 0));
}
}
}
}
int reponse = 1e18;
for (int i = 0; i < n; i++)
{
reponse = min(reponse, dp[n][i][a-1]);
}
return reponse;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |