Submission #680822

#	Time	Username	Problem	Language	Result	Execution time	Memory
680822		speedyArda	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	212 KiB

boxes

#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
long long delivery(int N, int K, int L, int p[]) {
    int pos = 0;
    while(p[pos] == 0 && pos < N)
        pos++;
    if(pos == N)
        return 0;
    ll ans = 1e18;
    ll temp = 0;
    int t_pos = pos;
    /*while(t_pos + K - 1 < N && p[t_pos + K - 1] <= L / 2)
    {
        temp += p[t_pos + K - 1] * 2; // Go and come
        t_pos += K;
    }*/
    int take = 0;
    while(t_pos < N && p[t_pos] <= L / 2)
    {
        take++;
        if(take == K)
        {
            take = 0;
            temp += p[t_pos] * 2;
        }
        t_pos++;
    }

    int oldtake = take;

    // Either give some souvenirs from other half or stop.
    //Begin with left side
    //cout << "G" << t_pos << "\n";
            // Don't go to other half
            int r_pos = N - 1;
            ll toadd = 0;
            if(take > 0)
                toadd += p[t_pos - 1] * 2;
            take = 0;
            while(r_pos >= t_pos)
            {
                //r_pos -= K;
                take++;
                if(take == K)
                {
                    take = 0;
                    toadd += (L - p[r_pos]) * 2LL;
                }
                r_pos--;
            }

            if(take > 0)
                toadd += (L - p[r_pos]) * 2LL;

           //cout << temp << " " << toadd << " " << t_pos << "\n";
            ans = min(ans, temp + toadd);

            // Go to other half
            toadd = 0;
            take = oldtake;
            while(take < K && t_pos < N)
            {
                t_pos++;
                take++;
            }
            if(take > 0)
                toadd += L;
            r_pos = N - 1;
            take = 0;
            while(r_pos >= t_pos)
            {
                //r_pos -= K;
                take++;
                if(take == K)
                {
                    take = 0;
                    toadd += (L - p[r_pos]) * 2LL;
                }
                r_pos--;
            }
            if(take > 0)
                toadd += (L - p[r_pos]) * 2LL;
            //cout << temp << " " << toadd << " " << t_pos << " " << p[t_pos] << "\n";
            //cout << temp << " " << toadd << "\n";
            ans = min(ans, temp + toadd);
    

    //Begin with right side
    r_pos = N - 1;
    temp = 0;
    take = 0;
    //toadd = 0;
    while(r_pos >= pos && p[r_pos] >= L / 2)
    {
        take++;
        if(take == K)
        {
            take = 0;
            temp += (L - p[r_pos]) * 2LL;
        }
        r_pos--;
    }
    oldtake = take;
    //Begin with right side
            // Don't go to other half
            int l_pos = pos;
            toadd = 0;
            if(take > 0)
                toadd += (L - p[r_pos + 1]) * 2;
            take = 0;
            while(l_pos <= r_pos)
            {
                //l_pos += K;
                take++;
                if(take == K)
                {
                    take = 0;
                    toadd += p[l_pos] * 2LL;
                }
                l_pos++;
            }
            if(take > 0)
                toadd += p[l_pos] * 2LL;
            ans = min(ans, temp + toadd);

            // Go to other half
            toadd = 0;
            l_pos = pos;
            take = oldtake;
            while(take < K && r_pos >= pos)
            {
                r_pos--;
                take++;
            }
            if(take > 0)
                toadd += L;
            take = 0;
            while(l_pos <= r_pos)
            {
                //l_pos += K;
                take++;
                if(take == K)
                {
                    take = 0;
                    toadd += p[l_pos] * 2LL;
                } 
                l_pos++;
            }
            if(take > 0)
                toadd += p[l_pos] * 2LL;
            ans = min(ans, temp + toadd);
   // ans = min(ans, temp);

    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30