# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
873937 | HuyQuang_re_Zero | Boxes with souvenirs (IOI15_boxes) | C++14 | 545 ms | 375340 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |