Submission #711937

#TimeUsernameProblemLanguageResultExecution timeMemory
711937bin9638Roller Coaster Railroad (IOI16_railroad)C++17
34 / 100
57 ms28232 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...