Submission #891832

#	Time	Username	Problem	Language	Result	Execution time	Memory
891832		12345678	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	450 ms	372404 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e7+5;
ll mnl[nx], mnr[nx], res=LLONG_MAX;

long long delivery(int N, int K, int L, int p[]) {
    vector<ll> v(N+2);
    for (int i=0; i<N; i++) v[i+1]=p[i];
    v[N+1]=L;
    for (int i=1; i<=N; i++)
    {
        mnr[i]=mnr[max(i-K, 0)]+v[i]+min(v[i], L-v[i]);
    }
    for (int i=N; i>=1; i--)
    {
        mnl[i]=mnl[min(N+1, i+K)]+(L-v[i])+min(v[i], L-v[i]);
    }
    for (int i=0; i<=N; i++) res=min(res, mnr[i]+mnl[i+1]);
    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