Submission #618959

#	Time	Username	Problem	Language	Result	Execution time	Memory
618959		mdn2002	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	45 ms	24096 KiB

boxes

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

long long n , k , l , a [10000007] , b [10000007] , adp [2003][2005] , bdp [2003][2005];
long long dlta ( long long x , long long y )
{
    return min ( abs ( x - y ) , l - 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 ++ )
    {
        for ( int j = 0 ; j <= n + 2 ; j ++ )
        {
            adp [i][j] = 1e18;
            bdp [i][j] = 1e18;
        }
        if ( i != n + 1 )
        {
            a [i] = p [ i - 1 ];
            b [i] = a [i];
        }
    }

    long long ans = 1e18;
    adp [0][k] = 0;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        for ( int j = 1 ; j < k ; j ++ )
        {
            long long nxt = j - 1 , ad = 0;
            if ( nxt == 0 )
            {
                nxt = k + 1;
                ad = dlta ( a [i] , 0 );
            }
            adp [i][nxt] = min ( adp [i][nxt] , adp [ i - 1 ][j] + dlta ( a [i] , a [ i - 1 ] ) + ad );
            adp [i][k] = min ( adp [i][k] , adp [i][nxt] + dlta ( a [i] , 0 ) );
        }
        adp [i][ k - 1 ] = min ( adp [i][ k - 1 ] , adp [ i - 1 ][k] + dlta ( a [i] , 0 ) );
        adp [i][k] = min ( adp [i][k] , adp [i][ k - 1 ] + dlta ( a [i] , 0 ) );
    }
    reverse ( a + 1 , a + n + 1 );

    bdp [0][k] = 0;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        for ( int j = 1 ; j < k ; j ++ )
        {
            long long nxt = j - 1 , ad = 0;
            if ( nxt == 0 )
            {
                nxt = k + 1;
                ad = dlta ( a [i] , 0 );
            }
            bdp [i][nxt] = min ( bdp [i][nxt] , bdp [ i - 1 ][j] + dlta ( a [i] , a [ i - 1 ] ) + ad );
            bdp [i][k] = min ( bdp [i][k] , bdp [i][nxt] + dlta ( a [i] , 0 ) );
        }
        bdp [i][ k - 1 ] = min ( bdp [i][ k - 1 ] , bdp [ i - 1 ][k] + dlta ( a [i] , 0 ) );
        bdp [i][k] = min ( bdp [i][k] , bdp [i][ k - 1 ] + dlta ( a [i] , 0 ) );
    }
    for ( int i = 0 ; i <= n ; i ++ )
    {
        long long ada = adp [i][k] , adb = bdp [ n - i ][k];
        for ( int j = 1 ; j <= k ; j ++ ) ada = min ( ada , adp [i][j] + dlta ( b [i] , 0 ) );
        for ( int j = 1 ; j <= k ; j ++ ) adb = min ( adb , bdp [ n - i ][j] + dlta ( a [ i + 1 ] , 0 ) );

        ans = min ( ans , ada + adb );
    }
    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