Submission #873937

#	Time	Username	Problem	Language	Result	Execution time	Memory
873937		HuyQuang_re_Zero	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	545 ms	375340 KiB

boxes

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "boxes.h"
using namespace std;
int n,i,a[20000005],k,L;
ll l[10000005],r[20000005];
ll delivery(int _n,int k,int L,int _a[])
{
    n=0;
    for(i=0;i<_n;i++)
        if(_a[i]!=0) a[++n]=_a[i];
    if(n==0) return 0;
    for(i=1;i<=n;i++) a[i+n]=a[i];

    ll res=round(1e18);
    deque <int> dq;
    dq.push_back(n+1);
    for(i=n;i>=1;i--)
    {
        if(dq.front()-i>k) dq.pop_front();
        l[i]=l[dq.front()]+L-a[i]+min(a[i],L-a[i]);
        while(dq.size()>0 && l[i]<l[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }

    while(dq.size()>0) dq.pop_back();
    dq.push_back(n);
    for(i=n+1;i<=2*n;i++)
    {
        if(i-dq.front()>k) dq.pop_front();
        r[i]=r[dq.front()]+a[i]+min(a[i],L-a[i]);
        while(dq.size()>0 && r[i]<r[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }

    for(i=n;i<=2*n;i++)
    {
        res=min(res,r[i]+l[i-n+1]);
    }
    return res;
}

/*
int main()
{
    freopen("boxes.inp","r",stdin);
    freopen("boxes.out","w",stdout);
    int a[101];
    cin>>n>>k>>L;
    for(i=0;i<n;i++) cin>>a[i];
    cout<<delivery(n,k,L,a);
}
*/

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:20:30: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   20 | ll delivery(int _n,int k,int L,int _a[])
      |                          ~~~~^
boxes.cpp:18:23: note: shadowed declaration is here
   18 | int n,i,a[20000005],k,L;
      |                       ^
boxes.cpp:20:24: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   20 | ll delivery(int _n,int k,int L,int _a[])
      |                    ~~~~^
boxes.cpp:18:21: note: shadowed declaration is here
   18 | int n,i,a[20000005],k,L;
      |                     ^

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