제출 #1081989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081989		raphael_heuchl	선물상자 (IOI15_boxes)	C++14	50 / 100	2029 ms	22408 KiB

boxes

#include "boxes.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define INF 1'000'000'000'000'000'000

std::vector<long long> people;
long long n, l, k;
long long pos = 0;
long long sum = 0;

long long dist(long long curr, long long next = 0)
{
    long long d = std::abs(people[curr] - people[next]);
    return std::min(d, l - d);
}

void forward()
{
    sum += dist(pos, pos + 1);
    ++pos;
}

void fetch()
{
    sum += dist(pos) + dist(pos + 1);
    ++pos;
}

long long delivery(int N, int K, int L, int p[])
{
    n = N, k = K, l = L;
    people.push_back(0);
    for (int i = 0; i < N; ++i)
        people.push_back(p[i]);
    std::sort(people.begin(), people.end());
    people.push_back(0);

    long long best = INF;
    for (int i = 1; i <= K; ++i)
    {
        sum = 0;
        pos = 0;

        for (int j = 0; j < i; ++j)
            forward();
            
        while (pos <= N)
        {
            fetch();
            for (int j = 0; j < K-1; ++j)
            {
                if (pos > N)
                    break;
                forward();
            }
        }
        best = std::min(sum, best);
    }


    return best;
}

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