#include "boxes.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define ll long long
#define vl vector<ll>
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MOD=1000000007,N=1e7+10;
const char en='\n';
const ll LLINF=1ll<<60;
ll time1[N],time2[N],ans;
int n1,n2;
ll f(int r)
{
int lo=max(0,r-n2),hi=min(n1,r)-1;
while (lo<hi)
{
int mid=(lo+hi)/2;
int i=mid,i1=mid+1;
ll x=time1[n1-i]+time2[n2-(r-i)];
i=i1;
ll y=time1[n1-i]+time2[n2-(r-i)];
if (x<=y) hi=mid;
else lo=mid+1;
}
int i=lo;
ll k=time1[n1-i]+time2[n2-(r-i)];
ll k1=LLINF;
int hi1=min(n1,r);
if (i<hi1)
{
++i;
k1=time1[n1-i]+time2[n2-(r-i)];
}
return min(k,k1)*2;
}
ll f1(int r)
{
ll k=LLINF;
for (int i=max(0,r-n2);i<=min(n1,r);++i) k=min(k,time1[n1-i]+time2[n2-(r-i)]);
return k*2;
}
ll delivery(int n, int k, int l, int p[]) {
vi h1,h2;
for (int i=0;i<n;++i) if (p[i]*2<l) h1.pb(p[i]);
else h2.pb(p[i]);
reverse(h2.begin(),h2.end());
for (int&a: h2) a=l-a;
n1=h1.size();
n2=h2.size();
for (int i=0;i<min(k,n1);++i) time1[i+1]=h1[i];
for (int i=k;i<n1;++i) time1[i+1]=h1[i]+time1[i-k+1];
for (int i=0;i<min(k,n2);++i) time2[i+1]=h2[i];
for (int i=k;i<n2;++i) time2[i+1]=h2[i]+time2[i-k+1];
//for (int i=0;i<=n1;++i) cout<<time1[i]<<' ';
//cout<<endl;
//for (int i=0;i<=n2;++i) cout<<time2[i]<<' ';
//cout<<endl;
ans=(n+k-1)/k*1ll*l;
for (int fc=0;fc*k<=n;++fc)
{
if (k<=100) ans=min(ans,f(fc*k)+fc*1ll*l);
else ans=min(ans,f1(fc*k)+fc*1ll*l);
}
return ans;
}
Compilation message
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:56:12: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
n1=h1.size();
~~~~~~~^~
boxes.cpp:57:12: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
n2=h2.size();
~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
404 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
404 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
404 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
135 ms |
25848 KB |
Output is correct |
34 |
Correct |
176 ms |
19936 KB |
Output is correct |
35 |
Correct |
86 ms |
18516 KB |
Output is correct |
36 |
Correct |
60 ms |
25940 KB |
Output is correct |
37 |
Correct |
80 ms |
25952 KB |
Output is correct |
38 |
Correct |
281 ms |
26720 KB |
Output is correct |
39 |
Correct |
127 ms |
24420 KB |
Output is correct |
40 |
Correct |
185 ms |
19684 KB |
Output is correct |
41 |
Correct |
59 ms |
25952 KB |
Output is correct |
42 |
Correct |
37 ms |
20064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
404 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
380 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
135 ms |
25848 KB |
Output is correct |
34 |
Correct |
176 ms |
19936 KB |
Output is correct |
35 |
Correct |
86 ms |
18516 KB |
Output is correct |
36 |
Correct |
60 ms |
25940 KB |
Output is correct |
37 |
Correct |
80 ms |
25952 KB |
Output is correct |
38 |
Correct |
281 ms |
26720 KB |
Output is correct |
39 |
Correct |
127 ms |
24420 KB |
Output is correct |
40 |
Correct |
185 ms |
19684 KB |
Output is correct |
41 |
Correct |
59 ms |
25952 KB |
Output is correct |
42 |
Correct |
37 ms |
20064 KB |
Output is correct |
43 |
Correct |
648 ms |
215624 KB |
Output is correct |
44 |
Correct |
357 ms |
192796 KB |
Output is correct |
45 |
Correct |
1681 ms |
184636 KB |
Output is correct |
46 |
Correct |
590 ms |
216908 KB |
Output is correct |
47 |
Correct |
703 ms |
217092 KB |
Output is correct |
48 |
Correct |
603 ms |
217552 KB |
Output is correct |
49 |
Correct |
576 ms |
193640 KB |
Output is correct |
50 |
Correct |
448 ms |
192604 KB |
Output is correct |
51 |
Correct |
598 ms |
202584 KB |
Output is correct |
52 |
Correct |
374 ms |
182864 KB |
Output is correct |