Submission #67910

#	Time	Username	Problem	Language	Result	Execution time	Memory
67910		theknife2001	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	690 ms	243492 KiB

boxes

#include "boxes.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define mid (l+r)/2


using namespace std;
const int N=1e7+55;
long long dp[N][2];
int p[N];
int n;
deque < long long > dq;



long long delivery(int N, int k, int L, int P[])
{
    int j=0;
    for(int i=0;i<N;i++)
    {
        if(!P[i])
            continue ;
        p[j++]=P[i];
    }
    if(j==0)
        return 0;
    n=j;
    int x=k;
    for(int i=0;i<n;i++)
    {
        if(i>=x)
        {
            dp[i][0]=dq.back()+p[i]+min(p[i],L-p[i]);
        }
        else
        {
            dp[i][0]=p[i]+min(p[i],L-p[i]);
        }
        while(dq.size()&&dq.front()>dp[i][0])
        {
            dq.pop_front();
        }
        dq.push_front(dp[i][0]);
        if(i-x>=0)
            if(dp[i-x][0]==dq.back())
                dq.pop_back();
    }
    for(int i=n-1;i>=0;i--)
    {
        if(i+x<n)
        {
            dp[i][1]=dq.back()+(L-p[i])+min(p[i],L-p[i]);
        }
        else
        {
            dp[i][1]=L-p[i]+min(p[i],L-p[i]);
        }
        while(dq.size()&&dq.front()>dp[i][1])
        {
            dq.pop_front();
        }
        dq.push_front(dp[i][1]);
        if(i+x<n)
            if(dp[i+x][1]==dq.back())
                dq.pop_back();
    }
    long long ans=dp[0][1];
    for(int i=0;i<n;i++)
    {
        ans=min(dp[i][0]+((i+1<n)?(dp[i+1][1]):0),ans);
    }
    return ans;
}
/*
10 5 100
1 5 20 35 41 42 55 56 57 58
*/

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:16:48: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 long long delivery(int N, int k, int L, int P[])
                                                ^
boxes.cpp:8:11: note: shadowed declaration is here
 const int N=1e7+55;
           ^

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