제출 #619042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619042		mdn2002	선물상자 (IOI15_boxes)	C++14	100 / 100	994 ms	369608 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 dlta ( long long x , long long y )
{
    if ( y == 0 || x == 0 ) return min ( abs ( x - y ) , l - abs ( x - y ) );
    return abs ( x - y );
}
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;
    deque < pair < long long , int > > dq;
    dq . push_back ( { 0 , 0 } );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        adp [i] = min ( adp [i] , dq [0] . first + 2 * a [i] );
        while ( dq . size () )
        {
            long long x = ( * -- dq . end () ) . first;
            if ( x >= adp [i] ) dq . pop_back ();
            else break;
        }
        dq . push_back ( { adp [i] , i } );
        if ( i - k >= dq [0] . second ) dq . pop_front ();
    }
    reverse ( a + 1 , a + n + 1 );

    dq . clear ();
    dq . push_back ( { 0 , 0 } );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        bdp [i] = min ( bdp [i] , dq [0] . first + 2 * ( l - a [i] ) );
        while ( dq . size () )
        {
            long long x = ( * -- dq . end () ) . first;
            if ( x >= bdp [i] ) dq . pop_back ();
            else break;
        }
        dq . push_back ( { bdp [i] , i } );
        if ( i - k >= dq [0] . second ) dq . pop_front ();
    }
    for ( int i = 0 ; i <= n ; i ++ )
    {
        long long ada = adp [i] - b [i] + dlta ( b [i] , 0 ) , adb = bdp [ n - i ] - ( l - a [ n - i ] ) + dlta ( a [ n - i ] , 0 );
        adb = max ( adb , 0ll );
        ans = min ( ans , ada + adb );
        //cout << ' ' << i << ' ' << ada << ' ' << adb << endl;
    }
    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