제출 #619004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619004		mdn2002	선물상자 (IOI15_boxes)	C++14	10 / 100	1 ms	340 KiB

boxes

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

long long n , k , l , a [10000007] , b [10000007] , adp [10000007] , bdp [10000007];
long long delivery(int N, int K, int L, int p[]) {
    n = N , k = K , l = L;
    for ( int i = 1 ; i <= n + 1 ; i ++ )
    {
        adp [i] = 1e18;
        bdp [i] = 1e18;
        if ( i != n + 1 )
        {
            a [i] = p [ i - 1 ];
            b [i] = a [i];
        }
    }

    long long ans = 1e18;
    multiset < long long > ms;
    ms . insert ( 0 );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        adp [i] = min ( adp [i] , * ms . begin () + 2 * a [i] );
        ms . insert ( adp [i] );
        if ( i - k >= 0 ) ms . erase ( ms . lower_bound ( adp [ i - k ] ) );
    }
    reverse ( a + 1 , a + n + 1 );

    ms . clear ();
    ms . insert ( 0 );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        bdp [i] = min ( bdp [i] , * ms . begin () + 2 * ( l - a [i] ) );
        ms . insert ( bdp [i] );
        if ( i - k >= 0 ) ms . erase ( ms . lower_bound ( bdp [ i - k ] ) );
    }
    for ( int i = 0 ; i <= n ; i ++ )
    {
        ans = min ( ans , adp [i] + bdp [ n - i ] );
    }
    return ans;
}

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