제출 #282477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282477		SamAnd	선물상자 (IOI15_boxes)	C++17	100 / 100	816 ms	248184 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 10000007;

int n, k;
int a[N];
ll p[N], s[N];

long long delivery(int N_, int K, int L, int A[])
{
    n = N_;
    k = K;

    for (int i = 1; i <= n; ++i)
        a[i] = A[i - 1];

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i)
        p[i] = p[max(0, i - k)] + a[i] * 2;

    for (int i = n; i >= 1; --i)
        s[i] = s[min(n + 1, i + k)] + (L - a[i]) * 2;

    ll ans = min(s[1], p[n]);

    if (n <= k)
        ans = min(ans, (ll)L);

    for (int i = 0; i <= n; ++i)
        ans = min(ans, p[i] + s[i + 1]);

    for (int l = 1; l <= n - k + 1; ++l)
    {
        int r = l + k - 1;
        ans = min(ans, p[l - 1] + s[r + 1] + L);
    }

    return ans;
}

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