제출 #100110

#제출 시각아이디문제언어결과실행 시간메모리
100110shenxyRoller Coaster Railroad (IOI16_railroad)C++11
0 / 100
81 ms9088 KiB
#include "railroad.h" #include <vector> #include <algorithm> #include <utility> #include <cstring> #define INF 1000000000000000000LL using namespace std; int n; vector< pair<int, int> > speeddat; long long int dptable[17][(1 << 16) - 1]; int LSOne(int i) { return i & (-i); } int logtwo(int i) { int ans = 0; while (i) { ans += 1; i >>= 1; } return ans; } long long int speeddp(int sp, int mask) { if (mask == 0) return 0; if (dptable[sp][mask] != -1LL) return dptable[sp][mask]; long long int ans = INF; int temp = mask; while (temp) { int X = LSOne(temp); if (sp == 0) { ans = min(ans, speeddp(logtwo(X), mask & (~X))); } else { ans = min(ans, speeddp(logtwo(X), mask & (~X)) + max(0, speeddat[logtwo(X) - 1].second - speeddat[sp - 1].first)); } temp = temp & (~X); } return dptable[sp][mask] = ans; } long long int plan_roller_coaster(vector<int> s, vector<int> t) { n = s.size(); for (int i = 0; i < n; i++) { speeddat.push_back(make_pair(t[i], s[i])); } if (n > 16) { return 0; } else { memset(dptable, -1LL, sizeof(dptable)); return speeddp(0, (1 << n) - 1); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...