Submission #138864

#TimeUsernameProblemLanguageResultExecution timeMemory
138864RiscadoARoller Coaster Railroad (IOI16_railroad)C++14
0 / 100
77 ms3528 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 = 0x7FFFFFFFFFFFFFFF; else s = S[next]; long long v = 0x7FFFFFFFFFFFFFFF; for (int i = 0, j = 1; i < MAX_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); }

Compilation message (stderr)

railroad.cpp: In function 'long long int calc(int, int)':
railroad.cpp:25:29: warning: overflow in implicit constant conversion [-Woverflow]
                         s = 0x7FFFFFFFFFFFFFFF;
                             ^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...