Submission #680833

#	Time	Username	Problem	Language	Result	Execution time	Memory
680833		speedyArda	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	340 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;
    int take = 0;
    while(t_pos < N && p[t_pos] <= L / 2)
    {
        take++;
        t_pos++;
    }

    int oldtake = take;

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

            // Go to other half
            toadd = 0;
            take = oldtake;
            while(take < K && t_pos < N)
            {
                t_pos++;
                take++;
            }
            last_l = t_pos - 1;
            while(last_l >= 0)
            {
                toadd += p[last_l] * 2LL;
                last_l -= K;
            }
            last_r = t_pos;
            while(last_r < N)
            {
                toadd += (L - p[last_r]) * 2LL;
                last_r += K;
            }

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

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

            //int l_pos = pos;
            toadd = 0;
            take = oldtake;
            while(r_pos >= 0 && take < K)
            {
                //l_pos += K;
                take++;
                r_pos--;
            }
            last_l = r_pos;
            last_r = r_pos + 1;
            while(last_l >= 0)
            {
                toadd += p[last_l] * 2LL;
                last_l -= K;
            }
            while(last_r < N)
            {
                toadd += (L - p[last_r]) * 2LL;
                last_r += K;
            }
           //cout << temp << " " << toadd << " " << p[r_pos] << " " << r_pos << "\n";
            ans = min(ans, 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