Submission #446579

#	Time	Username	Problem	Language	Result	Execution time	Memory
446579		FEDIKUS	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	538 ms	195988 KiB

boxes

#include "boxes.h"

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e7+10;
ll bn[maxn];
ll bp[maxn];

ll delivery(int n, int k, int l, int p[]) {
    ll ret=LLONG_MAX;
    int koliko=0;
    for(int i=0;i<n;i++){
        if(p[i]==0){
            koliko++;
        }else p[i-koliko]=p[i];
    }
    n-=koliko;
    for(int i=0;i<n;i++){
        if(i-k<0) bn[i]=2*p[i];
        else{
            bn[i]=bn[i-k]+2*p[i];
        }
    }
    for(int i=n-1;i>=0;i--){
        if(i+k>=n) bp[i]=2*(l-p[i]);
        else{
            bp[i]=bp[i+k]+2*(l-p[i]);
        }
    }
    for(int i=-1;i<n;i++){
        ret=min(ret,(i>=0 ? bn[i]:0)+(i+1<n ? bp[i+1]:0));
    }
    for(int i=-1;i<n;i++){
        ret=min(ret,(i>=0 ? bn[i]:0)+l+(i+k+1<n ? bp[i+k+1]:0));
    }
    return ret;
}

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