Submission #101350

#	Time	Username	Problem	Language	Result	Execution time	Memory
101350		ansol4328	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	617 ms	242020 KiB

boxes

#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

int m[10000005];
ll dp1[10000005], dp2[10000005];

ll delivery(int N, int K, int L, int *positions)
{
    for(int i=N ; i>0 ; i--) m[i]=positions[i-1];
    for(int i=1 ; i<=N ; i++)
    {
        if(i<K) dp1[i]=m[i]+min(m[i],L-m[i]);
        else dp1[i]=dp1[i-K]+m[i]+min(m[i],L-m[i]);
    }
    for(int i=N ; i>=1 ; i--)
    {
        if(N-i<K) dp2[i]=(L-m[i])+min(m[i],L-m[i]);
        else dp2[i]=dp2[i+K]+(L-m[i])+min(m[i],L-m[i]);
    }
    ll res=dp1[0]+dp2[1];
    for(int i=1 ; i<=N ; i++) res=min(res,dp1[i]+dp2[i+1]);
    return res;
}

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