제출 #138868

#제출 시각아이디문제언어결과실행 시간메모리
138868RiscadoARoller Coaster Railroad (IOI16_railroad)C++14
0 / 100
75 ms3604 KiB
#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 -1; 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)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...