#include "railroad.h"
const int INF = 1000000001;
const int MAX_N = 16;
const int MAX_MASK = 0xFFFF;
int N, S[MAX_N], T[MAX_N];
long long dp[MAX_N + 1][MAX_MASK];
inline long long max(long long a, long long b)
{
return a > b ? a : b;
}
inline long long min(long long a, long long b)
{
return a < b ? a : b;
}
long long calc(int next, int mask)
{
if (dp[next][mask] == -1) {
int s;
if (next == MAX_N)
s = INF;
else
s = S[next];
long long v = 0x7FFFFFFFFFFFFFFF;
for (int i = 0, j = 1; i < N; ++i, j <<= 1)
if (mask & j)
v = min(v, max(0, T[i] - s) + calc(i, mask & (~j)));
dp[next][mask] = v;
}
return dp[next][mask];
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
N = (int)s.size();
if (N > 16)
return 0;
for (int i = 0; i < N; ++i) {
S[i] = s[i];
T[i] = t[i];
}
for (int i = 0; i <= N; ++i) {
dp[i][0] = 0;
for (int m = 1; m < MAX_MASK; ++m)
dp[i][m] = -1;
}
return calc(MAX_N, 0xFFFF >> (16 - N));
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
n = 2 |
2 |
Correct |
3 ms |
1784 KB |
n = 2 |
3 |
Correct |
3 ms |
1784 KB |
n = 2 |
4 |
Correct |
3 ms |
1784 KB |
n = 2 |
5 |
Correct |
3 ms |
1784 KB |
n = 2 |
6 |
Incorrect |
3 ms |
1912 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
n = 2 |
2 |
Correct |
3 ms |
1784 KB |
n = 2 |
3 |
Correct |
3 ms |
1784 KB |
n = 2 |
4 |
Correct |
3 ms |
1784 KB |
n = 2 |
5 |
Correct |
3 ms |
1784 KB |
n = 2 |
6 |
Incorrect |
3 ms |
1912 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
3404 KB |
n = 199999 |
2 |
Incorrect |
73 ms |
3448 KB |
answer is not correct: 0 instead of 1 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
n = 2 |
2 |
Correct |
3 ms |
1784 KB |
n = 2 |
3 |
Correct |
3 ms |
1784 KB |
n = 2 |
4 |
Correct |
3 ms |
1784 KB |
n = 2 |
5 |
Correct |
3 ms |
1784 KB |
n = 2 |
6 |
Incorrect |
3 ms |
1912 KB |
answer is not correct: 0 instead of 523688153 |
7 |
Halted |
0 ms |
0 KB |
- |