Submission #136976

#	Time	Username	Problem	Language	Result	Execution time	Memory
136976		arthurconmy	Boxes with souvenirs (IOI15_boxes)	C++14	Compilation error	0 ms	0 KiB

boxes

#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 (stderr)

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