Submission #446582

#	Time	Username	Problem	Language	Result	Execution time	Memory
446582		FEDIKUS	선물상자 (IOI15_boxes)	C++17	100 / 100	518 ms	196036 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;
    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