Submission #1082192

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

boxes

#include "boxes.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define INF 1'000'000'000'000'000'000
#define ABS(a) ((a) > 0 ? (a) : -(a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

std::vector<long long> people;
long long l;

inline long long dist(long long curr, long long next = 0)
{
    return MIN(ABS(people[curr] - people[next]), l - ABS(people[curr] - people[next]));
}

long long delivery(int N, int K, int L, int p[])
{
    l = L;
    people.resize(N+2);
    people[0] = 0;
    for (int i = 0; i < N; ++i)
        people[i+1] = p[i];
    people[N+1] = 0;

    long long root[N+2]{};
    long long next[N+2]{};
    long long kDist[N+2]{};

    for (int i = 0; i <= N; ++i)
        root[i] = MIN(people[i], l - people[i]),
        next[i] = MIN(ABS(people[i] - people[i+1]), l - ABS(people[i] - people[i+1]));
    for (int i = 0; i <= N; ++i)
        kDist[i] = (i+K-1 <= N ? people[i+K-1] : L) - people[i];
    
    long long best = INF;
    for (int i = 1; i <= K; ++i)
    {
        long long sum = 0;
        int pos = 0;
        sum += (pos+i <= N ? people[pos+i] : L) - people[pos];
        pos += i;

        while (pos <= N)
        {
            sum += root[pos];
            sum += root[++pos];
            sum += kDist[pos];
            pos += K-1;
        }

        best = std::min(best, sum);
    }

    return best;
}

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