#include "railroad.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int lent(vector<signed> s, 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;
}
long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
int n = (int) s.size();
if (n <= 16) return lent(s, t);
int avant = 0;
int fin = 1e18;
set<pair<int,int>> rails;
for (int i = 0; i < n; i++)
{
rails.insert(make_pair(s[i], i));
}
for (int i = 0; i < n; i++)
{
auto it = rails.lower_bound(make_pair(avant, -1));
if (it == rails.end()) {
return 42;
}
int r = it->second;
rails.erase(it);
auto it2 = rails.lower_bound(make_pair(t[r], -1));
if (it2 == rails.end()) {
if (t[r] <= fin) {
fin = s[r];
}
else {
return 42;
}
}
else {
avant = t[r];
}
}
return 0;
}
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
| ^~~~
# | 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... |