Submission #101348

#	Time	Username	Problem	Language	Result	Execution time	Memory
101348		ansol4328	Boxes with souvenirs (IOI15_boxes)	C++11	20 / 100	8 ms	388 KiB

boxes

#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

ll dp1[10000005], dp2[10000005];

ll delivery(int N, int K, int L, int *positions)
{
    for(int i=N ; i>0 ; i--) positions[i]=positions[i-1];
    for(int i=1 ; i<=N ; i++)
    {
        if(i<K) dp1[i]=positions[i]+min(positions[i],L-positions[i]);
        else dp1[i]=dp1[i-K]+positions[i]+min(positions[i],L-positions[i]);
    }
    for(int i=N ; i>=1 ; i--)
    {
        if(N-i<K) dp2[i]=(L-positions[i])+min(positions[i],L-positions[i]);
        else dp2[i]=dp2[i+K]+(L-positions[i])+min(positions[i],L-positions[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: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30