Submission #1085477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085477		alexdd	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	636 ms	333176 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long dple[10000005],dpri[10000005];
vector<int> a;
long long delivery(int N, int K, int L, int p[])
{
    a.push_back(0);
    for(int i=0;i<N;i++)
        if(p[i]!=0)
            a.push_back(p[i]);
    N = (int)a.size()-1;
    a.push_back(L);
    K = min(K, N);
    if(N==0)
    {
        return 0;
    }
    for(int r=0;r<K;r++)
    {
        dple[r] = a[r]*2;
        for(int i=r+K;i<=N;i+=K)
            dple[i] = dple[i-K] + a[i]*2;
    }
    for(int r=0;r<K;r++)
    {
        dpri[r] = (L-a[N-r+1])*2;
        for(int i=r+K;i<=N;i+=K)
            dpri[i] = dpri[i-K] + (L-a[N-i+1])*2;
    }
    long long rez=INF;
    for(int cntle=0;cntle<=N;cntle++)
    {
        if(a[cntle] >= (L+1)/2 || a[min(N+1,cntle+K)] < (L+1)/2)
            continue;
        for(int cntc=0;cntle+cntc*K<=N;cntc++)
        {
            int cntri = N - cntle - cntc*K;
            rez = min(rez, dple[cntle] + dpri[cntri] + 1LL*L*cntc);
        }
    }
    return rez;
}
/*
3 2 8
1 2 5
output: 10

*/

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