# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1264199 | vtnoo | Roller Coaster Railroad (IOI16_railroad) | C++20 | 40 ms | 11592 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN=16;
const long long INF=1e18;
long long dp[1<<MAXN][MAXN];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t){
int n=s.size();
for(int i=0;i<(1<<MAXN);i++){
for(int j=0;j<MAXN;j++)dp[i][j]=INF;
}
for(int i=0;i<n;i++){
dp[1<<i][i]=0;
}
for(int S=1;S<(1<<n);S++){
for(int i=0;i<n;i++){
if(S&(1<<i)){
for(int j=0;j<n;j++){
if(i==j)continue;
int prevS=(S^(1<<i));
if(dp[prevS][j]==INF)continue;
if(S&(1<<j)){
dp[S][i]=min(dp[S][i], dp[prevS][j]+max(0LL,(long long)t[j]-(long long)s[i]));
}
}
}
}
}
//cout<<dp[(1<<n)-1].second<<endl;
long long ret=INF;
for(int i=0;i<n;i++)ret=min(ret,dp[(1<<n)-1][i]);
return ret;
}
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... |