Submission #891826

#	Time	Username	Problem	Language	Result	Execution time	Memory
891826		12345678	선물상자 (IOI15_boxes)	C++17	50 / 100	87 ms	65972 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e3+5;
ll dpl[nx][nx], dpr[nx][nx], 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;
    sort(v.begin(), v.end());
    for (int i=1; i<=N; i++) mnr[i]=mnl[i]=LLONG_MAX;
    for (int i=1; i<=N; i++)
    {
        for (int j=0; j+1<K; j++) dpr[i][j]=dpr[i-1][j+1]+v[i]-v[i-1];
        dpr[i][K-1]=mnr[i-1]+v[i];
        for (int j=0; j<K; j++) mnr[i]=min(mnr[i], dpr[i][j]+min(v[i], L-v[i]));
    }
    for (int i=N; i>=1; i--)
    {
        for (int j=0; j+1<K; j++) dpl[i][j]=dpl[i+1][j+1]+v[i+1]-v[i];
        dpl[i][K-1]=mnl[i+1]+L-v[i];
        //cout<<"here "<<i<<' ';
        //for (int j=0; j<K; j++) cout<<dpl[i][j]<<' ';
        //cout<<'\n';
        for (int j=0; j<K; j++) mnl[i]=min(mnl[i], dpl[i][j]+min(v[i], L-v[i]));
    }
    for (int i=0; i<=N; i++) res=min(res, mnr[i]+mnl[i+1]);
    //for (int i=1; i<=N; i++) cout<<i<<' '<<mnl[i]<<' '<<mnr[i]<<'\n';
    return res;
}

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