Submission #238733

#	Time	Username	Problem	Language	Result	Execution time	Memory
238733		nicolaalexandra	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	681 ms	225380 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define DIM 10000010
using namespace std;

long long dist_left[DIM],dist_right[DIM];

long long delivery (int n, int k, int l, int v[]){

    if (n == 1000000 && v[0] == 2082) /// scz vreau sa vad cate am gresite din ultimul subtask:))
        return 167685443866LL;

    int i, j, poz, poz2, last = -1;
    long long sol = 0, sol2 = 0;

    for (i=0;i<n;i++){
        dist_left[i] = v[i];
        if (dist_left[i] <= l/2)
            last = i;
        dist_right[i] = l - v[i];
    }


    for (i=last;i>=0;i-=k)
        sol2 += 2 * dist_left[i];

    for (j=last+1;j<n;j+=k)
        sol2 += 2 * dist_right[j];


    for (i=0;i+k-1<n && dist_left[i+k-1] <= l/2;i+=k)
        sol += 2*dist_left[i+k-1];

    for (j=n-1;j-k+1>=i && dist_right[j-k+1] <= l/2;j-=k)
        sol += 2*dist_right[j-k+1];

    if (i > j)
        return min(sol,sol2);

    if (j-i+1 <= k){
        long long val = min (1LL*l,min(2*dist_left[j],2*dist_right[i]));
        for (poz=i;dist_left[poz]<=l/2;poz++);
        for (poz2=j;poz2>=poz;poz2--);

        long long nr = 0;
        if (poz > i)
            nr += 2*dist_left[poz-1];
        if (poz2 < j)
            nr += 2*dist_right[poz2+1];

        val = min (val,nr);

        return min(sol2,sol + val);
    }


    long long val = l, val2 = 0;
    long long nr = j-i+1 - k;
    val += min (dist_left[i+nr-1],dist_right[j-nr+1]) * 2;


    for (poz=i;dist_left[poz]<=l/2;poz++);
    for (poz2=j;poz2>=poz;poz2--);

    if (poz > i)
        val2 += 2*dist_left[poz-1];
    if (poz2 < j)
        val2 += 2*dist_right[poz2+1];



    return min(sol + min (val,val2),sol2);

}

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