| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1354891 | dsg | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "boxes.h"
#include <vector>
#include <algorithm>
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
// Sử dụng long long để tránh tràn số vì N=10^7 và L=10^9
// Khởi tạo mảng tính chi phí tích lũy từ bên trái và bên phải
// N có thể lên tới 10^7, dùng vector có kích thước N+1
vector<long long> left(N + 1, 0);
vector<long long> right(N + 1, 0);
// Tính left[i]: Quãng đường tối thiểu để lấy i món quà đầu tiên (chiều kim đồng hồ)
for (int i = 1; i <= N; i++) {
// Vị trí quà thứ i nằm ở chỉ số i-1 trong mảng p
if (i <= K) {
left[i] = 2LL * p[i - 1];
} else {
left[i] = left[i - K] + 2LL * p[i - 1];
}
}
// Tính right[i]: Quãng đường tối thiểu để lấy i món quà từ cuối lên (ngược chiều kim đồng hồ)
for (int i = 1; i <= N; i++) {
// Vị trí quà xa nhất tính từ bên phải
if (i <= K) {
right[i] = 2LL * (L - p[N - i]);
} else {
right[i] = right[i - K] + 2LL * (L - p[N - i]);
}
}
// Trường hợp 1: Không có chuyến đi nào đi trọn một vòng
long long ans = 2e18; // Một số cực lớn
for (int i = 0; i <= N; i++) {
ans = min(ans, left[i] + right[N - i]);
}
// Trường hợp 2: Có đúng một chuyến đi vòng quanh (quãng đường L)
// Chuyến đi này sẽ lấy tối đa K món quà nằm ở giữa
for (int i = 0; i <= N; i++) {
// Lấy i món từ trái, N-i-K món từ phải, còn lại K món ở giữa đi 1 vòng
int remains = max(0, N - i - K);
ans = min(ans, left[i] + (long long)L + right[remains]);
}
return ans;
}