#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
/*
Roughly three choices:
- Go left and deliver B presents and return on left
- Go right and deliver B presents and return on right
- Go in a circle and deliver as many presents as possible
Idea:
Have a prefix time taken to give first i from left
Have a prefix time taken to give first i from right
A circle takes L time
for o in [0..n/k]:
find optimal value if we have o circles
*/
constexpr int maxn = 1e7 + 5;
ll left_side[maxn] = { 0 }, right_side[maxn] = { 0 };
long long delivery(int N, int K, int L, int p[]) {
int n = N, k = K, l = L;
// Calculate if going left
for (int y = 0; y < n; y+= k)
{
for (int i = 1; i <= k; i++)
{
if (i + y > n) break;
// cout << p[i + y - 1] << "\n";
left_side[y + i] = left_side[max(0, i + y - k)] + p[i + y - 1] + min(p[i + y - 1], l - p[i + y - 1]);
}
}
// Calculate if going right
for (int y = 0; y < n; y+= k)
{
for (int i = 1; i <= k; i++)
{
if (i + y > n) break;
// cout << p[n - (i + y)] << "\n";
right_side[i + y] = right_side[max(0, i + y - k)] + (l - p[n - (i + y)]) + min(p[n - (i + y)], l - p[n - (i + y)]);
}
}
// for (int i = 0; i <= n; i++) cout << left_side[i] << " ";
// cout << "\n";
// for (int i = 0; i <= n; i++) cout << right_side[i] << " ";
// cout << "\n";
ll output = (1ll << 62);
for (int i = 0; i <= n; i++)
{
output = min(output, left_side[i] + right_side[n - i]);
}
// cerr << output << endl;
return output;
}
