| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1354894 | dsg | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "boxes.h"
#include <algorithm>
#include <vector>
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
// cw[i] là chi phí đi theo chiều kim đồng hồ lấy i món quà đầu tiên và quay về 0
// ccw[i] là chi phí đi ngược chiều kim đồng hồ lấy i món quà cuối cùng và quay về 0
vector<long long> cw(N + 1, 0);
vector<long long> ccw(N + 1, 0);
// Tính chi phí tích lũy theo chiều kim đồng hồ
for (int i = 1; i <= N; i++) {
if (i <= K) {
cw[i] = 2LL * p[i - 1];
} else {
cw[i] = cw[i - K] + 2LL * p[i - 1];
}
}
// Tính chi phí tích lũy theo ngược chiều kim đồng hồ
for (int i = 1; i <= N; i++) {
if (i <= K) {
ccw[i] = 2LL * (L - p[N - i]);
} else {
ccw[i] = ccw[i - K] + 2LL * (L - p[N - i]);
}
}
// Khởi tạo ans bằng trường hợp không đi vòng tròn (chỉ đi từ 2 phía rồi quay lại)
long long ans = 4e18; // Một số cực lớn (tương đương LLONG_MAX nhưng an toàn hơn khi cộng)
// Trường hợp 1: Không có chuyến đi vòng tròn nào (quãng đường L)
for (int i = 0; i <= N; i++) {
ans = min(ans, cw[i] + ccw[N - i]);
}
// Trường hợp 2: Có đúng một chuyến đi vòng quanh thế giới (mất chi phí L)
// Chuyến đi vòng 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, K món ở giữa đi 1 vòng
int j = N - i - K;
if (j < 0) j = 0;
ans = min(ans, cw[i] + (long long)L + ccw[j]);
}
return ans;
}