Submission #1020669

#TimeUsernameProblemLanguageResultExecution timeMemory
1020669vjudge1Roller Coaster Railroad (IOI16_railroad)C++17
34 / 100
36 ms8792 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define rall(s) s.rbegin(), s.rend() #define all(s) s.begin(), s.end() #define sz(s) (int)s.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const ll inf = 1e18; long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { int n = sz(s); if (n <= 16) { ll dp[1 << n][n]; for (int msk = 0; msk < (1 << n); msk++) { for (int i = 0; i < n; i++) { dp[msk][i] = inf; } } for (int i = 0; i < n; i++) dp[1 << i][i] = 0; for (int msk = 1; msk < (1 << n); msk++) { for (int i = 0; i < n; i++) { if (msk >> i & 1) { for (int j = 0; j < n; j++) { if (msk >> j & 1) continue; int msk1 = msk + (1 << j); dp[msk1][j] = min(dp[msk1][j], dp[msk][i] + max(0, t[i] - s[j])); } } } } ll ans = inf; for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i]); return ans; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...