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 "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 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... |