#include "boxes.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S Second
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
using namespace :: std;
const ll maxn=3e7+500;
const ll inf=1e17+900;
ll sagh(ll n,ll k){return (n/k)+(n%k!=0);}
ll dp[maxn];
long long delivery(int n, int k, int L, int p[]) {
fill(dp,dp+maxn,inf);
k=min(k,n);
ll u=n%k;
for(ll i=0;i<k;i++){
vector<ll> l,r,vec;l.reserve(n/k+2);r.reserve(n/k+2);
for(ll j=i+k-1;j<n;j+=k){
l.pb(p[j]);
}
ll ii=(u-i+k)%k;
ll cnt=1;
for(ll j=n-ii-k;j>=0;j-=k){
r.pb(L-p[j]);
}
ll ct=0;
if(i)ct+=p[i-1];
if(ii)ct+=(L-p[n-ii]);
for(auto v:l)vec.pb(v);
for(auto v:r)vec.pb(v);
sort(vec.begin(),vec.end());
ll pr=ct;
for(ll j=0;j<vec.size();j++){
dp[j*k+i+ii]=min(dp[j*k+i+ii],pr);
pr+=vec[j];
}
dp[vec.size()*k+i+ii]=min(dp[vec.size()*k+i+ii],pr);
}
ll ans=sagh(n,k)*L;
for(ll i=0;i*k<=n;i++){
ans=min(ans,dp[n-i*k]*2+L*i);
}
return ans;
}
Compilation message
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<vec.size();j++){
~^~~~~~~~~~~
boxes.cpp:30:5: warning: unused variable 'cnt' [-Wunused-variable]
ll cnt=1;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
235128 KB |
Output is correct |
2 |
Correct |
185 ms |
235128 KB |
Output is correct |
3 |
Correct |
182 ms |
235128 KB |
Output is correct |
4 |
Correct |
188 ms |
235248 KB |
Output is correct |
5 |
Correct |
187 ms |
235288 KB |
Output is correct |
6 |
Correct |
186 ms |
235152 KB |
Output is correct |
7 |
Correct |
190 ms |
235216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
235144 KB |
Output is correct |
2 |
Correct |
185 ms |
235256 KB |
Output is correct |
3 |
Correct |
187 ms |
235176 KB |
Output is correct |
4 |
Correct |
186 ms |
235120 KB |
Output is correct |
5 |
Correct |
185 ms |
235168 KB |
Output is correct |
6 |
Correct |
185 ms |
235100 KB |
Output is correct |
7 |
Correct |
185 ms |
235244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
187 ms |
235168 KB |
Output is correct |
2 |
Correct |
186 ms |
235232 KB |
Output is correct |
3 |
Correct |
199 ms |
235100 KB |
Output is correct |
4 |
Correct |
186 ms |
235256 KB |
Output is correct |
5 |
Correct |
188 ms |
235232 KB |
Output is correct |
6 |
Correct |
187 ms |
235284 KB |
Output is correct |
7 |
Correct |
187 ms |
235132 KB |
Output is correct |
8 |
Correct |
189 ms |
235176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
235128 KB |
Output is correct |
2 |
Correct |
185 ms |
235128 KB |
Output is correct |
3 |
Correct |
182 ms |
235128 KB |
Output is correct |
4 |
Correct |
188 ms |
235248 KB |
Output is correct |
5 |
Correct |
187 ms |
235288 KB |
Output is correct |
6 |
Correct |
186 ms |
235152 KB |
Output is correct |
7 |
Correct |
190 ms |
235216 KB |
Output is correct |
8 |
Correct |
185 ms |
235144 KB |
Output is correct |
9 |
Correct |
185 ms |
235256 KB |
Output is correct |
10 |
Correct |
187 ms |
235176 KB |
Output is correct |
11 |
Correct |
186 ms |
235120 KB |
Output is correct |
12 |
Correct |
185 ms |
235168 KB |
Output is correct |
13 |
Correct |
185 ms |
235100 KB |
Output is correct |
14 |
Correct |
185 ms |
235244 KB |
Output is correct |
15 |
Correct |
187 ms |
235168 KB |
Output is correct |
16 |
Correct |
186 ms |
235232 KB |
Output is correct |
17 |
Correct |
199 ms |
235100 KB |
Output is correct |
18 |
Correct |
186 ms |
235256 KB |
Output is correct |
19 |
Correct |
188 ms |
235232 KB |
Output is correct |
20 |
Correct |
187 ms |
235284 KB |
Output is correct |
21 |
Correct |
187 ms |
235132 KB |
Output is correct |
22 |
Correct |
189 ms |
235176 KB |
Output is correct |
23 |
Correct |
187 ms |
235124 KB |
Output is correct |
24 |
Correct |
187 ms |
235256 KB |
Output is correct |
25 |
Correct |
186 ms |
235128 KB |
Output is correct |
26 |
Correct |
186 ms |
235248 KB |
Output is correct |
27 |
Correct |
188 ms |
235140 KB |
Output is correct |
28 |
Correct |
185 ms |
235128 KB |
Output is correct |
29 |
Correct |
187 ms |
235128 KB |
Output is correct |
30 |
Correct |
191 ms |
235240 KB |
Output is correct |
31 |
Correct |
189 ms |
235260 KB |
Output is correct |
32 |
Correct |
188 ms |
235128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
235128 KB |
Output is correct |
2 |
Correct |
185 ms |
235128 KB |
Output is correct |
3 |
Correct |
182 ms |
235128 KB |
Output is correct |
4 |
Correct |
188 ms |
235248 KB |
Output is correct |
5 |
Correct |
187 ms |
235288 KB |
Output is correct |
6 |
Correct |
186 ms |
235152 KB |
Output is correct |
7 |
Correct |
190 ms |
235216 KB |
Output is correct |
8 |
Correct |
185 ms |
235144 KB |
Output is correct |
9 |
Correct |
185 ms |
235256 KB |
Output is correct |
10 |
Correct |
187 ms |
235176 KB |
Output is correct |
11 |
Correct |
186 ms |
235120 KB |
Output is correct |
12 |
Correct |
185 ms |
235168 KB |
Output is correct |
13 |
Correct |
185 ms |
235100 KB |
Output is correct |
14 |
Correct |
185 ms |
235244 KB |
Output is correct |
15 |
Correct |
187 ms |
235168 KB |
Output is correct |
16 |
Correct |
186 ms |
235232 KB |
Output is correct |
17 |
Correct |
199 ms |
235100 KB |
Output is correct |
18 |
Correct |
186 ms |
235256 KB |
Output is correct |
19 |
Correct |
188 ms |
235232 KB |
Output is correct |
20 |
Correct |
187 ms |
235284 KB |
Output is correct |
21 |
Correct |
187 ms |
235132 KB |
Output is correct |
22 |
Correct |
189 ms |
235176 KB |
Output is correct |
23 |
Correct |
187 ms |
235124 KB |
Output is correct |
24 |
Correct |
187 ms |
235256 KB |
Output is correct |
25 |
Correct |
186 ms |
235128 KB |
Output is correct |
26 |
Correct |
186 ms |
235248 KB |
Output is correct |
27 |
Correct |
188 ms |
235140 KB |
Output is correct |
28 |
Correct |
185 ms |
235128 KB |
Output is correct |
29 |
Correct |
187 ms |
235128 KB |
Output is correct |
30 |
Correct |
191 ms |
235240 KB |
Output is correct |
31 |
Correct |
189 ms |
235260 KB |
Output is correct |
32 |
Correct |
188 ms |
235128 KB |
Output is correct |
33 |
Correct |
289 ms |
239048 KB |
Output is correct |
34 |
Correct |
252 ms |
239096 KB |
Output is correct |
35 |
Correct |
285 ms |
251116 KB |
Output is correct |
36 |
Correct |
279 ms |
239068 KB |
Output is correct |
37 |
Correct |
301 ms |
239224 KB |
Output is correct |
38 |
Correct |
300 ms |
239224 KB |
Output is correct |
39 |
Correct |
286 ms |
239224 KB |
Output is correct |
40 |
Correct |
301 ms |
239212 KB |
Output is correct |
41 |
Correct |
303 ms |
239388 KB |
Output is correct |
42 |
Correct |
268 ms |
239160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
235128 KB |
Output is correct |
2 |
Correct |
185 ms |
235128 KB |
Output is correct |
3 |
Correct |
182 ms |
235128 KB |
Output is correct |
4 |
Correct |
188 ms |
235248 KB |
Output is correct |
5 |
Correct |
187 ms |
235288 KB |
Output is correct |
6 |
Correct |
186 ms |
235152 KB |
Output is correct |
7 |
Correct |
190 ms |
235216 KB |
Output is correct |
8 |
Correct |
185 ms |
235144 KB |
Output is correct |
9 |
Correct |
185 ms |
235256 KB |
Output is correct |
10 |
Correct |
187 ms |
235176 KB |
Output is correct |
11 |
Correct |
186 ms |
235120 KB |
Output is correct |
12 |
Correct |
185 ms |
235168 KB |
Output is correct |
13 |
Correct |
185 ms |
235100 KB |
Output is correct |
14 |
Correct |
185 ms |
235244 KB |
Output is correct |
15 |
Correct |
187 ms |
235168 KB |
Output is correct |
16 |
Correct |
186 ms |
235232 KB |
Output is correct |
17 |
Correct |
199 ms |
235100 KB |
Output is correct |
18 |
Correct |
186 ms |
235256 KB |
Output is correct |
19 |
Correct |
188 ms |
235232 KB |
Output is correct |
20 |
Correct |
187 ms |
235284 KB |
Output is correct |
21 |
Correct |
187 ms |
235132 KB |
Output is correct |
22 |
Correct |
189 ms |
235176 KB |
Output is correct |
23 |
Correct |
187 ms |
235124 KB |
Output is correct |
24 |
Correct |
187 ms |
235256 KB |
Output is correct |
25 |
Correct |
186 ms |
235128 KB |
Output is correct |
26 |
Correct |
186 ms |
235248 KB |
Output is correct |
27 |
Correct |
188 ms |
235140 KB |
Output is correct |
28 |
Correct |
185 ms |
235128 KB |
Output is correct |
29 |
Correct |
187 ms |
235128 KB |
Output is correct |
30 |
Correct |
191 ms |
235240 KB |
Output is correct |
31 |
Correct |
189 ms |
235260 KB |
Output is correct |
32 |
Correct |
188 ms |
235128 KB |
Output is correct |
33 |
Correct |
289 ms |
239048 KB |
Output is correct |
34 |
Correct |
252 ms |
239096 KB |
Output is correct |
35 |
Correct |
285 ms |
251116 KB |
Output is correct |
36 |
Correct |
279 ms |
239068 KB |
Output is correct |
37 |
Correct |
301 ms |
239224 KB |
Output is correct |
38 |
Correct |
300 ms |
239224 KB |
Output is correct |
39 |
Correct |
286 ms |
239224 KB |
Output is correct |
40 |
Correct |
301 ms |
239212 KB |
Output is correct |
41 |
Correct |
303 ms |
239388 KB |
Output is correct |
42 |
Correct |
268 ms |
239160 KB |
Output is correct |
43 |
Correct |
1186 ms |
274296 KB |
Output is correct |
44 |
Correct |
793 ms |
274424 KB |
Output is correct |
45 |
Correct |
1485 ms |
412164 KB |
Output is correct |
46 |
Correct |
1080 ms |
274548 KB |
Output is correct |
47 |
Correct |
1016 ms |
274680 KB |
Output is correct |
48 |
Correct |
1690 ms |
274972 KB |
Output is correct |
49 |
Correct |
1138 ms |
274584 KB |
Output is correct |
50 |
Correct |
870 ms |
274488 KB |
Output is correct |
51 |
Correct |
993 ms |
274552 KB |
Output is correct |
52 |
Correct |
810 ms |
274516 KB |
Output is correct |