Submission #680804

#	Time	Username	Problem	Language	Result	Execution time	Memory
680804		speedyArda	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	308 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;
    }

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

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

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

    //Begin with right side
    ll r_pos = N - 1;
    temp = 0;
    while(r_pos - K + 1 >= pos && p[r_pos - K + 1] >= L / 2)
    {
        temp += p[r_pos - K + 1] * 2; // Go and come
        r_pos -= K;
    }

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

            ans = min(ans, temp + toadd);

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

    return ans;
}

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