Submission #777511

#	Time	Username	Problem	Language	Result	Execution time	Memory
777511		boris_mihov	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2062 ms	37612 KiB

boxes

#include "boxes.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 10000000 + 10;
const llong INF = 1e18;

int n, k, l;
std::vector <int> left;
std::vector <int> right;
llong prefix[MAXN];
llong suffix[MAXN];

llong calcLeft(int to)
{
    llong res = 0;
    for (int i = to ; i >= 0 ; i -= k)
    {
        res += 2 * left[i];
    }

    return res;
}

llong calcRight(int to)
{
    llong res = 0;
    for (int i = to ; i < n ; i += k)
    {
        res += 2 * right[i];
    }

    return res;
}

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

    if (k > n) k = n;
    for (int i = 0 ; i < n ; ++i)
    {
        left.push_back(p[i]);
        right.push_back(l - p[i]);
    }

    for (int i = 0 ; i < n ; ++i)
    {
        prefix[i] = 2 * left[i];
        if (i > 0)
        {
            prefix[i] += prefix[i - 1];
            if (i % k != 0)
            {
                prefix[i] -= 2 * left[i - 1];
            }
        }
    }

    for (int i = n - 1 ; i >= 0 ; --i)
    {
        suffix[i] = 2 * right[i];
        suffix[i] += suffix[i + 1];
        if ((n - 1 - i) % k != 0)
        {
            suffix[i] -= 2 * right[i + 1];
        }
    }

    llong ans = calcRight(0);
    for (int i = 0 ; i < n ; ++i)
    {
        ans = std::min(ans, calcLeft(i) + calcRight(i + 1));
    }
    
    for (int i = 0 ; i + k <= n ; ++i)
    {
        llong curr = l + calcRight(i + k);
        if (i > 0) curr += calcLeft(i - 1);
        ans = std::min(ans, curr);
    }

    return ans;
}

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