Submission #618906

#	Time	Username	Problem	Language	Result	Execution time	Memory
618906		mdn2002	Boxes with souvenirs (IOI15_boxes)	C++14	25 / 100	2041 ms	47748 KiB

boxes

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

long long n , k , l , a [10000007] , adp [1003][1003][3] , bdp [1003][1003][3];
vector < int > aa , bb;
long long dlta ( long long x , long long y )
{
    return min ( abs ( x - y ) , l - abs ( x - y ) );
}
long long af ( int x , int kk , int ze )
{
    int rl = aa [x];
    if ( ze ) rl = 0;
    if ( x == aa . size () - 1 ) return dlta ( rl , 0 );
    if ( adp [x][kk][ze] != -1 ) return adp [x][kk][ze];
    long long ans = 1e17;
    if ( kk != k ) ans = min ( ans , af ( x , k , 1 ) + dlta ( rl , 0 ) );
    if ( kk ) ans = min ( ans , af ( x + 1 , kk - 1 , 0 ) + dlta ( rl , aa [ x + 1 ] ) );
    return adp [x][kk][ze] = ans;
}
long long bf ( int x , int kk , int ze )
{
    int rl = bb [x];
    if ( ze ) rl = 0;
    if ( x == bb . size () - 1 ) return dlta ( rl , 0 );
    if ( bdp [x][kk][ze] != -1 ) return bdp [x][kk][ze];
    long long ans = 1e17;
    if ( kk != k ) ans = min ( ans , bf ( x , k , 1 ) + dlta ( rl , 0 ) );
    if ( kk ) ans = min ( ans , bf ( x + 1 , kk - 1 , 0 ) + dlta ( rl , bb [ x + 1 ] ) );
    return bdp [x][kk][ze] = ans;
}
long long f ( int x )
{
    long long ans = 0;
    aa . clear () , bb . clear ();
    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] );
    memset ( adp , -1 , sizeof adp );
    memset ( bdp , -1 , sizeof bdp );
    ans = af ( 0 , k , 0 ) + bf ( 0 , k , 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 af(int, int, int)':
boxes.cpp:15:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if ( x == aa . size () - 1 ) return dlta ( rl , 0 );
      |          ~~^~~~~~~~~~~~~~~~~~~
boxes.cpp:18:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |     if ( kk != k ) ans = min ( ans , af ( x , k , 1 ) + dlta ( rl , 0 ) );
      |                                               ^
boxes.cpp: In function 'long long int bf(int, int, int)':
boxes.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if ( x == bb . size () - 1 ) return dlta ( rl , 0 );
      |          ~~^~~~~~~~~~~~~~~~~~~
boxes.cpp:29:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |     if ( kk != k ) ans = min ( ans , bf ( x , k , 1 ) + dlta ( rl , 0 ) );
      |                                               ^
boxes.cpp: In function 'long long int f(int)':
boxes.cpp:39:60: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   39 |     for ( int i = 1 ; i <= x ; i ++ ) aa . push_back ( a [i] );
      |                                                        ~~~~^
boxes.cpp:40:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |     for ( int i = n ; i > x ; i -- ) bb . push_back ( a [i] );
      |                   ^
boxes.cpp:40:59: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   40 |     for ( int i = n ; i > x ; i -- ) bb . push_back ( a [i] );
      |                                                       ~~~~^
boxes.cpp:43:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |     ans = af ( 0 , k , 0 ) + bf ( 0 , k , 0 );
      |                    ^
boxes.cpp:43:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |     ans = af ( 0 , k , 0 ) + bf ( 0 , k , 0 );
      |                                       ^
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:19: note: shadowed declaration is here
    5 | long long n , k , l , a [10000007] , adp [1003][1003][3] , bdp [1003][1003][3];
      |                   ^
boxes.cpp:49:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |     int l = 0 , r = n , mid1 , mid2;
      |                     ^

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