#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
vector<long long> dp1,dp2;
vector<vector<long long> > suf;
dp1.resize(N);
dp2.resize(N);
dp1[0] = 2ll*p[0];
for(int i = 1; i < N; i++){
dp1[i] = i >= K ? dp1[i-K] : 0ll;
dp1[i] += 2ll*(long long)p[i];
}
dp2[N-1] = 2ll*(long long)(L-p[N-1]);
for(int i = N-2; i >= 0; i--){
dp2[i] = i+K >= N ? 0ll : dp2[i+K];
dp2[i] += 2ll*(long long)(L-p[i]);
}
for(int i = 0; i < K; i++){
suf.push_back(vector<long long>());
for(int j = 0; K*j+i < N; j++){
suf[i].push_back(0);
}
}
for(int i = 0; i < K; i++){
for(int j = (N-i-1)/K; j >= 0; j--){
suf[i][j] = min((K*(j+1)+i >= N ? (long long)1e18 : suf[i][j+1]),dp2[K*j+i] + (long long)j*(long long)L);
}
}
long long mn = (long long)(N+K-1)/(long long)K*(long long)L;
for(int i = 0; i < N; i++){
mn = min(mn,dp1[i] + (long long)(N-i+K-2)/(long long)K*(long long)L);
mn = min(mn,dp2[i] + (long long)(i+K-1)/(long long)K*(long long)L);
if(i == N-1) continue;
mn = min(mn,dp1[i] + suf[(i+1) % K][(i+1) / K] - (long long)(i+1)/(long long)K*(long long)L);
//for(int j = 0; i+1+j*K < N; j++){
// mn = min(mn,dp1[i] + dp2[i+1+j*K] + (long long)(j)*(long long)L);
//}
}
return mn;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
420 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
420 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
432 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
420 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 |
420 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 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 |
2 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 |
380 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
432 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
420 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 |
420 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 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 |
2 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 |
380 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
137 ms |
32116 KB |
Output is correct |
34 |
Correct |
95 ms |
31992 KB |
Output is correct |
35 |
Correct |
120 ms |
28868 KB |
Output is correct |
36 |
Correct |
121 ms |
32044 KB |
Output is correct |
37 |
Correct |
114 ms |
29560 KB |
Output is correct |
38 |
Correct |
109 ms |
29620 KB |
Output is correct |
39 |
Correct |
129 ms |
32096 KB |
Output is correct |
40 |
Correct |
97 ms |
31996 KB |
Output is correct |
41 |
Correct |
116 ms |
31480 KB |
Output is correct |
42 |
Correct |
105 ms |
29640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
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 |
432 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
420 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 |
420 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
22 |
Correct |
2 ms |
256 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 |
2 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 |
380 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
137 ms |
32116 KB |
Output is correct |
34 |
Correct |
95 ms |
31992 KB |
Output is correct |
35 |
Correct |
120 ms |
28868 KB |
Output is correct |
36 |
Correct |
121 ms |
32044 KB |
Output is correct |
37 |
Correct |
114 ms |
29560 KB |
Output is correct |
38 |
Correct |
109 ms |
29620 KB |
Output is correct |
39 |
Correct |
129 ms |
32096 KB |
Output is correct |
40 |
Correct |
97 ms |
31996 KB |
Output is correct |
41 |
Correct |
116 ms |
31480 KB |
Output is correct |
42 |
Correct |
105 ms |
29640 KB |
Output is correct |
43 |
Correct |
1412 ms |
360556 KB |
Output is correct |
44 |
Correct |
1288 ms |
341436 KB |
Output is correct |
45 |
Correct |
889 ms |
304036 KB |
Output is correct |
46 |
Correct |
1702 ms |
340956 KB |
Output is correct |
47 |
Correct |
1531 ms |
304216 KB |
Output is correct |
48 |
Correct |
1342 ms |
282612 KB |
Output is correct |
49 |
Correct |
1525 ms |
360512 KB |
Output is correct |
50 |
Correct |
1516 ms |
341152 KB |
Output is correct |
51 |
Correct |
1853 ms |
358208 KB |
Output is correct |
52 |
Correct |
1470 ms |
311948 KB |
Output is correct |