Submission #1264199

#TimeUsernameProblemLanguageResultExecution timeMemory
1264199vtnooRoller Coaster Railroad (IOI16_railroad)C++20
34 / 100
40 ms11592 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)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...