Submission #618848

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

boxes

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

int n , k , l , a [10000007];
long long dlta ( int x , int y )
{
    return min ( abs ( x - y ) , l - abs ( x - y ) );
}
long long f ( int x )
{
    long long ans = 0 , kk = k;
    deque < int > aa , bb;
    aa . push_back ( 0 );
    bb . push_back ( 0 );
    for ( int i = 1 ; i <= x ; i ++ ) aa . push_back ( a [i] );
    for ( int i = n ; i > x ; i -- ) bb . push_back ( a [i] );
    aa . push_back ( 0 );
    bb . push_back ( 0 );
    for ( int i = 1 ; i < aa . size () ; i ++ )
    {
        kk --;
        ans += dlta ( aa [i] , aa [ i - 1 ] );
        if ( kk == 0 )
        {
            kk = k;
            ans += dlta ( aa [i] , 0 );
            aa [i] = 0;
        }
    }
    kk = k;
    for ( int i = 1 ; i < bb . size () ; i ++ )
    {
        kk --;
        ans += dlta ( bb [i] , bb [ i - 1 ] );
        if ( kk == 0 )
        {
            kk = k;
            ans += dlta ( bb [i] , 0 );
            bb [i] = 0;
        }
    }
    return ans;
}

long long delivery(int N, int K, int L, int p[]) {
    n = N , k = K , l = L;
    for ( int i = 1 ; i <= n ; i ++ ) a [i] = p [ i - 1 ];
    int l = 0 , r = n , mid1 , mid2;
    while ( r - l > 100 )
    {
        mid1 = l + ( r - l ) / 3;
        mid2 = r - ( r - l ) / 3;
        long long cst1 = f ( mid1 ) , cst2 = f ( mid2 );
        if ( cst1 < cst2 ) r = mid2;
        else l = mid1;
    }
    long long ans = 1e18;
    for ( int i = l ; i <= r ; i ++ ) ans = min ( ans , f ( i ) );
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int f(int)':
boxes.cpp:20:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for ( int i = 1 ; i < aa . size () ; i ++ )
      |                       ~~^~~~~~~~~~~~~~
boxes.cpp:32:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for ( int i = 1 ; i < bb . size () ; i ++ )
      |                       ~~^~~~~~~~~~~~~~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:49:9: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   49 |     int l = 0 , r = n , mid1 , mid2;
      |         ^
boxes.cpp:5:13: note: shadowed declaration is here
    5 | int n , k , l , a [10000007];
      |             ^

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