Submission #618870

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

boxes

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

int n , k , l , a [10000007] , adp [1003][1003] , bdp [1003][1003];
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 )
{
    if ( x == aa . size () - 1 ) return dlta ( aa [x] , 0 );
    if ( adp [x][kk] != -1 ) return adp [x][kk];
    long long ans = 1e18;
    if ( kk != k ) ans = min ( ans , af ( x , k ) + 2 * dlta ( aa [x] , 0 ) );
    if ( kk ) ans = min ( ans , af ( x + 1 , kk - 1 ) + dlta ( aa [x] , aa [ x + 1 ] ) );
    return adp [x][kk] = ans;
}
long long bf ( int x , int kk )
{
    if ( x == bb . size () - 1 ) return dlta ( bb [x] , 0 );
    if ( bdp [x][kk] != -1 ) return bdp [x][kk];
    long long ans = 1e18;
    if ( kk != k ) ans = min ( ans , bf ( x , k ) + 2 * dlta ( bb [x] , 0 ) );
    if ( kk ) ans = min ( ans , bf ( x + 1 , kk - 1 ) + dlta ( bb [x] , bb [ x + 1 ] ) );
    return bdp [x][kk] = ans;
}
long long f ( int x )
{
    long long ans = 0 , kk = k;
    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 ) + bf ( 0 , k );
    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)':
boxes.cpp:13:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if ( x == aa . size () - 1 ) return dlta ( aa [x] , 0 );
      |          ~~^~~~~~~~~~~~~~~~~~~
boxes.cpp:18:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |     return adp [x][kk] = ans;
      |                          ^~~
boxes.cpp: In function 'long long int bf(int, int)':
boxes.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if ( x == bb . size () - 1 ) return dlta ( bb [x] , 0 );
      |          ~~^~~~~~~~~~~~~~~~~~~
boxes.cpp:27:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |     return bdp [x][kk] = ans;
      |                          ^~~
boxes.cpp: In function 'long long int f(int)':
boxes.cpp:31:25: warning: unused variable 'kk' [-Wunused-variable]
   31 |     long long ans = 0 , kk = k;
      |                         ^~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:46:9: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   46 |     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] , bdp [1003][1003];
      |             ^

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