Submission #792135

#	Time	Username	Problem	Language	Result	Execution time	Memory
792135		BT21tata	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	467 ms	263336 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;
const ll N=1e7+5;

ll ans, l[N], r[N];

ll delivery(int n, int k, int L, int p[])
{
    for(int i=0; i<n; i++)
    {
        ans+=2*min(p[i], L-p[i]);
        if(i-k<0) l[i]=p[i]*2;
        else l[i]=l[i-k]+p[i]*2;
    }

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

    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