제출 #384709

#제출 시각아이디문제언어결과실행 시간메모리
384709qpwoeirut선물상자 (IOI15_boxes)C++17
10 / 100
1 ms364 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define idx first #define cost second typedef long long ll; typedef pair<ll,ll> pll; const ll INF = 1e18; ll delivery(int n, int k, int l, int p[]) { const ll N = n, K = k, L = l; deque<pll> lft, rht; lft.emplace_back(0LL, 0LL); rht.emplace_back(0LL, 0LL); for (int i=1; i<=N; ++i) { while (lft.size() > 0 && lft.front().idx + K < i) lft.pop_front(); while (rht.size() > 0 && rht.front().idx + K < i) rht.pop_front(); if (p[i-1] <= L/2) { assert(lft.size() > 0); const ll cur = lft.front().cost + 2LL * p[i-1]; if (i == N) return cur; if (p[i] <= L/2) { while (lft.size() > 0 && lft.back().cost >= cur) lft.pop_back(); lft.emplace_back(i, cur); } else { while (rht.size() > 0 && rht.back().cost >= cur) rht.pop_back(); rht.emplace_back(i, cur); } } else { assert(lft.size() + rht.size() > 0); const ll from_left = lft.empty() ? INF : lft.front().cost + L; const ll from_right = rht.empty() ? INF : rht.front().cost + 2LL * (L - p[rht.front().idx]); const ll cur = min(from_left, from_right); if (i == N) return cur; while (rht.size() > 0 && rht.back().cost >= cur) rht.pop_back(); rht.emplace_back(i, cur); } } assert(0); }
#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...