| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 368025 | KoD | Boxes with souvenirs (IOI15_boxes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef LOCAL
#include "boxes.h"
#endif
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
#define int long long
template <class T>
using Vec = std::vector<T>;
constexpr long long INF = std::numeric_limits<long long>::max();
template <class Select>
Vec<int> smawk(const int R, const int C, const Select &select) {
const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
if (row.empty()) {
return { };
}
Vec<int> cs;
cs.reserve(row.size());
for (const auto c: column) {
while (!cs.empty() && select(row[cs.size() - 1], cs.back(), c)) {
cs.pop_back();
}
if (cs.size() < row.size()) {
cs.push_back(c);
}
}
Vec<int> rs;
rs.reserve(row.size() / 2);
for (int i = 1; i < (int) row.size(); i += 2) {
rs.push_back(row[i]);
}
const auto half = dfs(dfs, rs, cs);
Vec<int> ret(row.size());
int idx = 0;
for (int i = 0; i < (int) row.size(); ++i) {
if (i & 1) {
ret[i] = half[i / 2];
}
else {
ret[i] = cs[idx];
const auto next = (i + 1 == (int) row.size() ? cs.back() : half[i / 2]);
while (cs[idx] < next) {
idx += 1;
if (select(row[i], ret[i], cs[idx])) {
ret[i] = cs[idx];
}
}
}
}
return ret;
};
Vec<int> row(R);
std::iota(row.begin(), row.end(), 0);
Vec<int> column(C);
std::iota(column.begin(), column.end(), 0);
return dfs(dfs, row, column);
}
Vec<long long> convolve(const Vec<long long> &A, const Vec<long long> &B) {
const int N = (int) A.size();
const int M = (int) B.size();
const auto get = [&](const int i, const int j) {
return A[j] + B[i - j];
};
const auto select = [&](const int i, const int j, const int k) {
if (j > i || i >= M + j) return true;
if (k > i) return false;
return get(i, j) >= get(i, k);
};
Vec<long long> ret(N + M - 1);
const auto best = smawk(N + M - 1, N, select);
for (int i = 0; i < N + M - 1; ++i) {
ret[i] = get(i, best[i]);
}
return ret;
}
long long delivery(int N, int K, int Len, int P[]) {
Vec<int> left, right;
left.reserve(N);
right.reserve(N);
for (int i = 0; i < N; ++i) {
const auto l = P[i];
const auto r = Len - P[i];
if (l <= r) {
left.push_back(l);
}
else {
right.push_back(r);
}
}
std::reverse(right.begin(), right.end());
const int L = (int) left.size();
const int R = (int) right.size();
Vec<long long> dp_l(L + 1), dp_r(R + 1);
for (int i = 1; i <= L; ++i) {
dp_l[i] = dp_l[(i >= K ? i - K : 0)] + 2 * left[i - 1];
}
for (int i = 1; i <= R; ++i) {
dp_r[i] = dp_r[(i >= K ? i - K : 0)] + 2 * right[i - 1];
}
const auto dp = convolve(dp_l, dp_r);
long long ret = INF;
for (int i = 0; i <= N; ++i) {
const auto first = (long long) Len * ((N - i + K - 1) / K);
const auto second = dp[i];
ret = std::min(ret, first + second);
}
return ret;
}
#ifdef LOCAL
int main() {
int N, K, L;
std::cin >> N >> K >> L;
int P[100] = {};
for (int i = 0; i < N; ++i) {
std::cin >> P[i];
}
std::cout << delivery(N, K, L, P) << '\n';
return 0;
}
#endif