Submission #618886

#	Time	Username	Problem	Language	Result	Execution time	Memory
618886		mdn2002	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1707 ms	24192 KiB

boxes

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

int n , k , l , a [10000007] , adp [1003][1003][3] , bdp [1003][1003][3];
vector < int > aa , bb;
long long dlta ( int x , int 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 = 1e13;
    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 = 1e13;
    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:20:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |     return adp [x][kk][ze] = ans;
      |                              ^~~
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:31:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   31 |     return bdp [x][kk][ze] = ans;
      |                              ^~~
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] , adp [1003][1003][3] , bdp [1003][1003][3];
      |             ^

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