이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[]) {
deque<pll> lft, rht;
lft.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 + 2 * 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 + 2 * (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |