Submission #591738

#	Time	Username	Problem	Language	Result	Execution time	Memory
591738		APROHACK	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	484 ms	239276 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll INF = __LONG_LONG_MAX__;
int n, k, l;
int posicionCW[10000002];
ll CW[10000001], AW[10000002];

long long delivery(int N, int K, int L, int p[]) {
    n = N, k=K, l = L;
    for(int i = 0 ; i < n ; i ++)posicionCW[i]=p[i];
    for(int i = 0 ; i < n ; i ++){
        if(i+1<=k)CW[i]=2*posicionCW[i];
        else CW[i] = CW[i-k] + 2*posicionCW[i];
        //cout<<CW[i]<<" ";
    }
    //cout<<endl;
    for(int i = n-1 ; i >= 0 ; i--){
        if(i>=n-k)AW[i]=2*(l-posicionCW[i]);
        else AW[i] = AW[i+k] + 2* (l-posicionCW[i]);
        //cout<<AW[i]<< " ";
    }
    //cout<<endl;
    ll ans = AW[0];
    ans = min(ans, AW[0]- (l-posicionCW[0]) + posicionCW[0]);
    //ans = min(ans, CW[n-1] - posicionCW[n-1] + (l-posicionCW[n-1]));
    AW[n]=0;
    posicionCW[n]=l;

    for(int i = 0 ; i < n ; i++){
        
        ans = min(ans, CW[i] + AW[i+1]);
        ans = min (ans, CW[i] + AW[i+1]- abs(l-posicionCW[i+1]) + posicionCW[i+1]);
        ans = min(ans, CW[i] - posicionCW[i] + abs(l-posicionCW[i]) + AW[i+1]);
      // cout<<i<<" "<<ans<<endl;
    }
    
    return ans;


}

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