제출 #341037

#제출 시각아이디문제언어결과실행 시간메모리
34103712tqian선물상자 (IOI15_boxes)C++17
0 / 100
1 ms384 KiB
#include "boxes.h" #include <bits/stdc++.h> typedef long long ll; const ll INF = 1e18; struct MinDeque { int lo = 0, hi = -1; std::deque<std::pair<ll, int>> d; void ins(ll x) { // add to back while ((d).size() && d.back().first >= x) d.pop_back(); d.push_back({x, ++hi}); } void del() { // delete from front if (d.front().second == lo++) d.pop_front(); } ll get() { return (d).size() ? d.front().first : INF; } }; long long delivery(int N, int K, int L, int p[]) { using namespace std; ll ans = INF; MinDeque D1; MinDeque D2; D1.ins(0); D2.ins(2 * (L-p[0])); for (int i = 0; i < N; i++) { ll res = INF; res = min(res, D2.get()); res = min(res, D1.get() + min(L, 2*p[i])); if (i != N-1) { D1.ins(res); D2.ins(res+2*L-p[i+1]); } if (i >= K-1) { D1.del(); D2.del(); } if (i == N-1) ans = res; } return ans; }
#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...