Submission #230263

#	Time	Username	Problem	Language	Result	Execution time	Memory
230263		Arg_007	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	788 ms	227704 KiB

boxes

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("hard1.txt","r",stdin)
#define OUT freopen("hard1.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 1000005
#define FastIO  ios_base::sync_with_stdio(false); cin.tie(NULL)


using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii ;

#define maxn 10000005
#define mod 1000000007LL
#define lim 1000000000
#define INF 4500000000000000000LL

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#include "boxes.h"

i64 pref[maxn] , suf[maxn] ;

i64 delivery( int n , int k , int l , int p[] )
{
    sort(p,p+n) ;

    for(int i=0 ; i<n ; i++)
    {
        if( i<k ) pref[i] = 2*p[i] ;
        else pref[i] = 2*p[i] + pref[i-k] ;
    }


    for(int i=n-1 ; i>=0 ; i--)
    {
        if( n-i <= k ) suf[i] = 2*( l-p[i] ) ;
        else suf[i] = 2*(l-p[i]) + suf[i+k] ;
    }

    i64 ans = min( pref[n-1] , suf[0] ) ;

    for(int i=1 ; i<n ; i++) ans = min( pref[i-1] + suf[i] , ans ) ;

    for(int i=0 ; i+k-1 < n ; i++)
    {
        i64 ret = l ;
        if( i>0 ) ret += pref[i-1] ;
        if( i+k < n ) ret += suf[i+k] ;
        ans = min(ans,ret) ;
    }
    return ans ;
}
/*
int main()
{
    int p[] = {1,2,5} ;
    printf("%lld\n" , delivery(3,2,8,p) ) ;
}
*/

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