#include "boxes.h"
#include <bits/stdc++.h>
#define MAXN 1000015
#define INF (1LL << 62LL)
using namespace std;
typedef long long ll;
int N, K, L, lbound;
ll DP[MAXN], pre[MAXN], cost, ST[2 * MAXN];
vector < int > P;
void build ()
{
for ( int i = 0; i <= 2 * (N + 5); i++ )
ST[i] = INF;
}
ll qry ( ll l, ll r )
{
ll ans = INF;
for ( l += N + 1, r += N + 2; l < r; l>>=1, r>>=1 )
{
if ( l & 1 )
ans = min ( ans, ST[l++] );
if ( r & 1 )
ans = min ( ans, ST[--r] );
}
return ans;
}
void upd ( ll pos, ll x )
{
for ( pos += N + 1; pos; pos>>=1 )
ST[pos] = min ( ST[pos], x );
}
ll delivery ( int _n, int _k, int _l, int _p[] )
{
N = _n, K = _k, L = _l;
P.push_back ( 0 );
for ( int i = 0; i < N; i++ )
P.push_back ( _p[i] );
P.push_back ( L );
for ( int i = 1; i <= N + 1; i++ )
{
pre[i] = pre[i - 1] + (P[i] - P[i - 1]);
if ( 2 * P[i] < L )
lbound = i;
}
build();
upd ( N + 1, 0 );
for ( int i = N; i >= 1; i-- )
{
if ( i <= lbound )
{
DP[i] = min ( qry ( i + 1, lbound + 1 ), qry ( lbound + 2, i + K ) + min ( (ll)L, 2 * (pre[N + 1] - pre[i]) ) ), upd ( i, DP[i] + 2 * pre[i - 1] );
}
else
{
DP[i] = qry ( i + 1, i + K ) + min ( (ll)L, 2 * (pre[N + 1] - pre[i]) );
if ( i == lbound + 1 )
upd ( i, DP[i] + 2 * pre[i - 1] );
else
upd ( i, DP[i] );
}
}
return DP[1];
Compilation message
boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:71:14: error: expected '}' at end of input
return DP[1];
^
