Submission #1039296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039296		idas	Boxes with souvenirs (IOI15_boxes)	C++11	25 / 100	1 ms	348 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)

using namespace std;
typedef long long ll;

const ll LINF=1e18;
const int MxN=1e7+10;
int n, k, l;

long long delivery(int N, int K, int L, int P[]) {
    n=N; k=K; l=L;

    int neg=0;
    vector<int> p;
    FOR(i, 0, n)
    {
        if(P[i]==0){
            neg++;
            continue;
        }
        p.push_back(P[i]);
    }
    n-=neg;

    bool bad=false;
    FOR(i, 0, n) if(p[i]==l/2) bad=true;

    ll ans=LINF, tot=0;
    if((l&1) || !bad){
        FOR(z, 0, 2)
        {
            int mx=n;
            FOR(i, 0, n)
            {
                if(p[i]>l/2){
                    mx=i;
                    break;
                }
            }
//            cerr << "max: " << mx << endl;

            int st_in=(mx)%k-1;
            if(st_in>=0) tot+=p[st_in]*2;

            for(int i=st_in+k; i<mx; i+=k)
            {
                tot+=p[i]*2;
            }

            FOR(i, 0, n)
            {
                p[i]=l-p[i];
            }
            reverse(p.begin(), p.end());
        }
        ans=min(ans, tot);
    }

    tot=0;
    FOR(z, 0, 2)
    {
        int st_in=n%k-1;
        if(st_in>=0) tot+=p[st_in]*2;

        bool fnd=true, crossed=false;
        for(int i=st_in+k; i<n; i+=k){
            if(i==n-1) fnd=true;
            if(crossed) tot+=min(p[i], l-p[i]);
            else tot+=p[i];
            if(p[i]>=l/2) crossed=true;
            tot+=min(p[i], l-p[i]);
        }

        assert(fnd);

        ans=min(ans, tot);
        tot=0;

        FOR(i, 0, n)
        {
            p[i]=l-p[i];
        }
        reverse(p.begin(), p.end());
    }

    return ans;
}

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