This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///Subtask 2
///Dynamic Programming with bitmask
ll cost[17][17];
ll memo[100005][17];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n=s.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j==i) continue;
cost[i][j]=max(0,t[i]-s[j]);
}
}
for(ll m=3;m<=(1<<n)-1;m++){
for(int i=0;i<n;i++){
if(m & (1<<i)){
if(m == (1<<i)){
memo[m][i]=0;
continue;
}
memo[m][i]=LLONG_MAX;
ll before_m=m-(1<<i);
for(int j=0;j<n;j++){
if(j==i) continue;
if(before_m & (1<<j))
memo[m][i]=min(memo[m][i],memo[before_m][j]+cost[j][i]);
}
}
}
}
ll minimum=LLONG_MAX;
for(int i=0;i<n;i++){
minimum=min(minimum,memo[(1<<n)-1][i]);
}
return minimum;
}
# | 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... |