Submission #721309

#	Time	Username	Problem	Language	Result	Execution time	Memory
721309		beaconmc	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	70 ms	156832 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll dp1[10000001], dp2[10000001];

long long delivery(int N, int K, int L, int p[]) {
    FOR(i,0,10000001) dp1[i] = 0, dp2[i] = 0;
    ll pos = 0;
    ll prev = 0;
    ll sus = K+1;
    FOR(i,0,N){
        sus -= 1;
        if (sus == 0){
            sus = K+1;
            prev += min(abs(pos-0), abs(pos-L));
            pos = 0;
        }
        prev += min(abs(pos - p[i]), abs(L-abs(pos - p[i])));
        pos = p[i];
        dp1[i] = prev+min(abs(pos-0), abs(pos-L));
        
        if (p[i] == 0) sus = K+1;
    }
    pos = L;
    prev = 0;
    sus = K+1;
    FORNEG(i, N-1, -1){
        sus -= 1;


        if (sus == 0){

            sus = K+1;
            prev += min(abs(pos-0), abs(pos-L));
            pos = L;
        }

        
        prev += min(abs(pos - p[i]), abs(L-abs(pos - p[i])));
        pos = p[i];
        dp2[i] = prev+min(abs(pos-0), abs(pos-L));
        
        if (p[i] == 0) sus = K+1;
    }
    ll ans = dp2[0];
    FOR(i,0,N){


        ans = min(ans, dp1[i] + dp2[i+1]);
    }
    return ans;
}

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