Submission #44844

#TimeUsernameProblemLanguageResultExecution timeMemory
44844RayaBurong25_1Roller Coaster Railroad (IOI16_railroad)C++17
34 / 100
89 ms17556 KiB
#include "railroad.h" #include <stdio.h> #define INF 1e18 long long dp[65536][16]; long long min(long long a, long long b) { return (a < b)?a:b; } long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { int n = (int) s.size(); int i, j, k, l, cnt; for (i = 0; i < n; i++) dp[0][i] = INF; for (i = 1; i <= n; i++) { for (j = 0; j < (1 << n); j++) { k = j; cnt = 0; while (k > 0) { k -= k&-k; cnt++; } if (cnt != i) continue; for (k = 0; k < n; k++) { if ((j&(1 << k)) == 0) { dp[j][k] = INF; } else if ((j^(1 << k)) == 0) { dp[j][k] = 0; } else { dp[j][k] = INF; for (l = 0; l < n; l++) { dp[j][k] = min(dp[j][k], dp[j^(1 << k)][l] + (t[l] > s[k])*(t[l] - s[k])); } } // printf("dp[%d][%d] = %lld\n", j, k, dp[j][k]); } } } long long ans = INF; for (i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...