Submission #619022

#	Time	Username	Problem	Language	Result	Execution time	Memory
619022		mdn2002	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	2101 ms	496028 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;
    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 ++ )
    {
        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: 0 / 30