#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "boxes.h"
#endif
using namespace std;
using ll = long long;
const int MAXN = 10000001; // increase to 10^7 for last subtask
int locs[2][MAXN]; // the locations of the souvenirs on each side of the start
ll dp[2][MAXN];
int side_count[2];
ll ans[MAXN]; // MAXK == MAXN
ll CEIL(int a, int b)
{
if(a%b == 0) return ll(a/b);
return ll(a/b) + 1LL;
}
ll delivery(int n, int k, int l, int P[])
{
// intialise things
for(int i=0; i<MAXN; i++)
{
locs[0][i]=-1;
locs[1][i]=-1;
ans[i]=1e18;
}
// do things
if(n==1) return 2LL*ll(min(P[0],l-P[0]));
side_count[0]=0;
side_count[1]=0;
for(int i=0; i<n; i++)
{
if(P[i] <= int(l/2))
{
locs[0][++side_count[0]] = P[i];
//cout << "0: " << P[i] << endl;
}
else
{
locs[1][++side_count[1]] = l-P[i];
//cout << "1: " << l-P[i] << endl;
}
}
for(int ind=0; ind<=1; ind++) // compute both sides of the dp
{
for(int i=1; i<=side_count[ind]; i++)
{
// calculating dp[ind][i]
dp[ind][i] = 2*locs[ind][i] + dp[ind][max(0,i-k)];
// cout << ind << " " << i << " " << dp[ind][i] << endl;
// this easy ???
}
}
// now we need do the residues (mod k) bit
// should we add the excess residue here? I think yes
for(int cut=0; cut<=side_count[0]; cut++)
{
// possibly recalculate a minimum for ans[cut % k]
ll cur = dp[0][side_count[0]-cut];
cur += ll(l)*CEIL(cut,k);
// cout << cut << " " << cur << endl;
ans[cut%k] = min(ans[cut%k], cur);
}
ll ret=1e18;
int bigk=k;
while(bigk<1000000 && bigk != 0) bigk*=k; // PROBABLY CHANGE FOR LAST SUBTASK
if(big_k==1) bigk = 1000000;
for(int cut2=0; cut2<=side_count[1]; cut2++)
{
ll cur = dp[1][side_count[1]-cut2];
cur += ll(l)*ll(int(cut2/k)) + ans[(bigk-cut2)%k];
ret = min(ret,cur);
}
if(k>=n) ret=min(ret,ll(l));
return ret;
}
#ifdef ARTHUR_LOCAL
int A[MAXN];
int main()
{
A[0]=4;
cout << delivery(1,2,8,A) << endl;
}
#endif
Compilation message
boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:92:8: error: 'big_k' was not declared in this scope
if(big_k==1) bigk = 1000000;
^~~~~
boxes.cpp:92:8: note: suggested alternative: 'bigk'
if(big_k==1) bigk = 1000000;
^~~~~
bigk
