Submission #64640

#	Time	Username	Problem	Language	Result	Execution time	Memory
64640		Bodo171	선물상자 (IOI15_boxes)	C++14	100 / 100	562 ms	198944 KiB

boxes

#include "boxes.h"
#include <deque>
#include <iostream>
using namespace std;
const int nmax=10*1000*1000+5;
deque<int> dq;
long long val[nmax],dp[nmax];
int i,poz;
long long delivery(int N, int K, int L, int p[]) {
    for(i=1;i<=N;i++)
    {
        poz=max(i-K,0);
        dp[i]=min(L+dp[poz],2*p[i-1]+dp[poz]);
        val[i]=dp[i-1]+2*(L-p[i-1]);
        if((!dq.empty())&&i-K>=dq.front())
            dq.pop_front();
        while((!dq.empty())&&val[i]<val[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(!dq.empty())
            dp[i]=min(dp[i],val[dq.front()]);
    }
    return dp[N];
}

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