제출 #163604

#제출 시각아이디문제언어결과실행 시간메모리
163604shenxy선물상자 (IOI15_boxes)C++11
100 / 100
932 ms217368 KiB
#include "boxes.h" #include <algorithm> #include <deque> #include <utility> using namespace std; typedef pair<long long, int> ii; long long delivery(int N, int K, int L, int p[]) { deque<ii> dp1, dp2; long long dptable[N]; dp1.push_back(ii(0, -1)); dp2.push_back(ii(2 * (L - p[0]), -1)); for (int i = 0; i < N; ++i) { while (!dp1.empty() && dp1.front().second + K < i) dp1.pop_front(); while (!dp2.empty() && dp2.front().second + K < i) dp2.pop_front(); if (i >= K) dptable[i] = L + dptable[i - K]; else dptable[i] = L; if (!dp1.empty()) dptable[i] = min(dptable[i], dp1.front().first + 2 * p[i]); if (!dp2.empty()) dptable[i] = min(dptable[i], dp2.front().first); if (i != N - 1) { while (!dp1.empty() && dp1.back().first >= dptable[i]) dp1.pop_back(); dp1.push_back(ii(dptable[i], i)); while (!dp2.empty() && dp2.back().first >= dptable[i] + 2 * (L - p[i + 1])) dp2.pop_back(); dp2.push_back(ii(dptable[i] + 2 * (L - p[i + 1]), i)); } } return dptable[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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...