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 <bits/stdc++.h>
#ifndef SKY
#include "railroad.h"
#endif // SKY
using namespace std;
#define ll long long
#define pb push_back
#define N 200010
#define ii pair<ll,int>
#define fs first
#define sc second
int n;
ll dp[(1<<16)+10][17];
void selfmin(ll&u,ll v)
{
u=min(u,v);
}
ll plan_roller_coaster(vector<int> s, vector<int> t)
{
// for(auto u:s)cout<<u<<" ";
n=s.size();
// cout<<n<<endl;
memset(dp,0x3f3f,sizeof(dp));
for(int i=0;i<n;i++)
dp[(1<<i)][i]=0;
for(int mask=1;mask<(1<<n);mask++)
for(int i=0;i<n;i++)
if((mask>>i)&1)
{
// cout<<mask<<" "<<i<<" "<<dp[mask][i]<<endl;
for(int j=0;j<n;j++)
if(((mask>>j)&1)==0)
selfmin(dp[mask+(1<<j)][j],dp[mask][i]+1ll*max(0,t[i]-s[j]));
}
ll res=1e18;
for(int i=0;i<n;i++)
selfmin(res,dp[(1<<n)-1][i]);
return res;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
int n;
cin>>n;
vector<int>s,t;
for(int i=0;i<n;i++)
{
int A,B;
cin>>A>>B;
s.pb(A);
t.pb(B);
}
cout<<plan_roller_coaster(s,t);
}
#endif
# | 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... |