#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 1e7 + 10;
ll dpLeft[MAX_N], dpRight[MAX_N];
long long delivery(int N, int K, int L, int p[]) {
int n = N, k = K;
for(int i = 0; i < n; i ++) {
if(i >= k) {
dpLeft[i] = dpLeft[i - k] + min(L, 2 * p[i]);
} else {
dpLeft[i] = min(L, 2 * p[i]);
}
}
for(int i = n - 1; i >= 0; i --) {
if(i + k < n) {
dpRight[i] = dpRight[i + k] + min(L, 2 * L - 2 * p[i]);
} else {
dpRight[i] = min(L, 2 * L - 2 * p[i]);
}
}
ll ret = min(dpRight[0], dpLeft[n - 1]);
for(int i = 0; i < n - 1; i ++) {
chkmin(ret, dpLeft[i] + dpRight[i + 1]);
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
0 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
0 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
55 ms |
29560 KB |
Output is correct |
34 |
Correct |
22 ms |
21880 KB |
Output is correct |
35 |
Correct |
25 ms |
22384 KB |
Output is correct |
36 |
Correct |
56 ms |
29688 KB |
Output is correct |
37 |
Correct |
56 ms |
29692 KB |
Output is correct |
38 |
Correct |
55 ms |
29688 KB |
Output is correct |
39 |
Correct |
49 ms |
28152 KB |
Output is correct |
40 |
Correct |
30 ms |
23552 KB |
Output is correct |
41 |
Correct |
56 ms |
29692 KB |
Output is correct |
42 |
Correct |
32 ms |
23804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
0 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
55 ms |
29560 KB |
Output is correct |
34 |
Correct |
22 ms |
21880 KB |
Output is correct |
35 |
Correct |
25 ms |
22384 KB |
Output is correct |
36 |
Correct |
56 ms |
29688 KB |
Output is correct |
37 |
Correct |
56 ms |
29692 KB |
Output is correct |
38 |
Correct |
55 ms |
29688 KB |
Output is correct |
39 |
Correct |
49 ms |
28152 KB |
Output is correct |
40 |
Correct |
30 ms |
23552 KB |
Output is correct |
41 |
Correct |
56 ms |
29692 KB |
Output is correct |
42 |
Correct |
32 ms |
23804 KB |
Output is correct |
43 |
Correct |
546 ms |
292852 KB |
Output is correct |
44 |
Correct |
211 ms |
215544 KB |
Output is correct |
45 |
Correct |
240 ms |
223352 KB |
Output is correct |
46 |
Correct |
550 ms |
294004 KB |
Output is correct |
47 |
Correct |
545 ms |
293880 KB |
Output is correct |
48 |
Correct |
545 ms |
293880 KB |
Output is correct |
49 |
Correct |
484 ms |
278648 KB |
Output is correct |
50 |
Correct |
283 ms |
232568 KB |
Output is correct |
51 |
Correct |
549 ms |
294048 KB |
Output is correct |
52 |
Correct |
291 ms |
235256 KB |
Output is correct |