Submission #337082

#	Time	Username	Problem	Language	Result	Execution time	Memory
337082		blue	선물상자 (IOI15_boxes)	C++11	100 / 100	550 ms	196132 KiB

boxes

#include "boxes.h"
#include <iostream>
using namespace std;

long long ll(int a)
{
    return (long long)(a);
}

//#teams, capacity, #sections, position of each team
long long delivery(int N, int K, int L, int positions[])
{
    long long dp_inc[N]; //minimum time needed to cover all 0, 1, ... i and end up at positions[i]

    dp_inc[0] = ll(positions[0]);
    for(int i = 1; i < K; i++)
    {
        dp_inc[i] = positions[i];
    }
    for(int i = K; i < N; i++)
    {
        dp_inc[i] = dp_inc[i - K] + ll(positions[i - K]) + ll(positions[i]);
    }

    // for(int i = 0; i < N; i++) cout << dp_inc[i] << ' ';
    // cout << '\n';

    long long dp_dec[N];

    dp_dec[N-1] = L - positions[N-1];
    for(int i = N-2; i > N-K-1; i--)
    {
        dp_dec[i] = L - positions[i];
    }
    for(int i = N-K-1; i >= 0; i--)
    {
        dp_dec[i] = dp_dec[i + K] + ll(L - positions[i + K]) + ll(L - positions[i]);
    }

    long long res = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
    for(int i = 0; i < N-1; i++)
        res = min(res, dp_inc[i] + ll(min(positions[i], L - positions[i])) + dp_dec[i+1] + ll(min(positions[i+1], L - positions[i+1])));

    res = min(res, dp_inc[N-1] + ll(min(positions[N-1], L - positions[N-1])));
    res = min(res, dp_dec[0] + ll(min(positions[0], L - positions[0])));

    return res;
}

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