#include "boxes.h" #include <bits/stdc++.h> long long delivery(int N, int K, int L, int p[]) { long long ans; K = std::min(K, N); std::vector<long long> dist1, dist2; dist1.push_back(0), dist2.push_back(0); dist1.reserve(N / 2), dist2.reserve(N / 2); for (int i = 0; i < N; ++i) if (p[i] <= L / 2) dist1.push_back(p[i]); else dist2.push_back(L - p[i]); sort(dist1.begin(), dist1.end()), sort(dist2.begin(), dist2.end()); int a = (int)dist1.size(), b = (int)dist2.size(); std::vector<long long> pref1(a, 0), pref2(b, 0); for (int i = 1; i < a; ++i) pref1[i] = dist1[i] + ((i >= K) ? pref1[i - K] : 0); for (int i = 1; i < b; ++i) pref2[i] = dist2[i] + ((i >= K) ? pref2[i - K] : 0); ans = 2 * (pref1[a - 1] + pref2[b - 1]); for (int i = 1; i < K; ++i) if (i >= a) break; else if (K - i >= b) continue; else ans = std::min(ans, 2 * (pref1[a - i - 1]) + L + 2 * (pref2[b - (K - i) - 1])); return ans; } /* ! Why L is added? * Let say you have a ring with 3 Parts - each having size K * Left K1 + Right K3 + Middle K2 * For 0 to K2, End Of K2 is much shorter to continue in same direction. That's why L. */ // * Efficient Solution // long long delivery(int N, int K, int L, int p[]) // { // long long ans; // int it = std::lower_bound(p, p + N, (L + 1) / 2) - p; // auto get_prf = [&](int i) // { // long long res = 0; // for (; i >= 0; i -= K) // res += 2 * p[i]; // return res; // }; // auto get_suf = [&](int i) // { // long long res = 0; // for (; i < N; i += K) // res += 2 * (L - p[i]); // return res; // }; // ans = get_prf(it - 1) + get_suf(it); // for (int i = std::max(0, it - K); i < it; i++) // ans = std::min(ans, (long long)get_prf(i - 1) + L + get_suf(i + K)); // return ans; // } /* Why L is added? Let say you have a ring with 3 Parts - each having size K Left K1 + Right K3 + Middle K2 (For This K2 End To 0 is much shorter to continue in same direction) */