Submission #619757

#	Time	Username	Problem	Language	Result	Execution time	Memory
619757		yanndev	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	673 ms	318120 KiB

boxes

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

ll delivery(int n, int k, int L, int p[]) {
    vector<int> left {};
    vector<int> right {};
    for (int i = 0; i < n; i++) {
        if (p[i] > L / 2)
            right.push_back(p[i]);
        else
            left.push_back(p[i]);
    }
    if (!right.empty())
        reverse(right.begin(), right.end());

    vector<ll> mLeft {};
    vector<ll> mRight {};
    mLeft.push_back(0);
    mRight.push_back(0);

    for (int i = 0; i < (int)left.size(); i++) {
        mLeft.push_back(2 * left[i]);
        if (i + 1 > k)
            mLeft.back() += mLeft[i + 1 - k];
        //cout << "mleft " << mLeft.back() << '\n';
    }

    for (int i = 0; i < (int)right.size(); i++) {
        mRight.push_back(2 * (L - right[i]));
        if (i + 1 > k)
            mRight.back() += mRight[i + 1 - k];
    }

    ll ans = mLeft.back() + mRight.back();

    for (int lstLeft = (int)left.size() - k; lstLeft <= (int)left.size(); lstLeft++) {
        //cout << "lst " << lstLeft << '\n';
        int cutFromLeft = (int)left.size() - lstLeft;
        int lstRight = max(0, (int)right.size() - (k - cutFromLeft));
        ll cur = mLeft[lstLeft] + mRight[lstRight] + L;
        ans = min(ans, cur);
    }

    return ans;
}

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