#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+2;
int n,k,l;
int pos[N];
ll kje1(){
ll sol = 0;
for(int i = 0; i < n; i++){
ll dod = 2*min(pos[i],(int)l-pos[i]);
sol += dod;
}
return sol;
}
ll kjen(){
int sol = l;
sol = min(sol,2*(l-pos[0]));
for(int i = 0; i < n-1; i++){
int sta = 2*pos[i]+2*(l-pos[i+1]);
sol = min(sol,sta);
}
sol = min(sol,2*pos[n-1]);
return sol;
}
ll inace(){
ll sol1 = 0;
int a = l/2, b = (l+1)/2;
for(int i = 0; i < n; i += k){
int kraj = min(i+k-1,n-1);
/// sad gledas range pos-ova od i do kraj
if(pos[kraj] <= a) sol1 += (ll)2*pos[kraj];
else if(pos[i] >= b) sol1 += (ll)2*(l-pos[i]);
else sol1 += l;
}
ll sol2 = 0;
a = l/2, b = (l+1)/2;
for(int i = n-1; i >= 0; i -= k){
int poc = max(0,i-k+1);
/// sad gledas range pos-ova od poc do i
if(pos[i] <= a) sol2 += (ll)2*pos[i];
else if(pos[poc] >= b) sol2 += (ll)2*(l-pos[poc]);
else sol2 += l;
}
return min(sol1,sol2);
}
ll dp1[N],dp2[N];
ll nesto(){
int a = l/2,b = (l+1)/2;
for(int i = 0; i < n; i++){
//if(pos[i] > a) break;
dp1[i] = 1e18;
int sta = min(k,i+1);
dp1[i] = min(dp1[i],2*pos[i]+dp1[i-sta]);
/*for(int j = 1; j <= k && j <= i+1; j++){
dp1[i] = min(dp1[i],2*pos[i]+dp1[i-j]);
}*/
}
for(int i = n-1; i >= 0; i--){
//if(pos[i] < b) break;
dp2[i] = 1e18;
int sta = min(k,n-i);
dp2[i] = min(dp2[i],2*(l-pos[i])+dp2[i+sta]);
/*for(int j = 1; j <= k && j <= n-i; j++){
dp2[i] = min(dp2[i],2*(l-pos[i])+dp2[i+j]);
}*/
}
ll sol1 = dp2[0];
for(int i = 0; i < n; i++) sol1 = min(sol1,dp1[i]+dp2[i+1]);
ll sol2 = 1e18;
for(int i = 0; i < n; i++){
int kraj = min(n-1,i+k-1);
if(pos[i] <= a && pos[kraj] >= b){
ll sta = l;
if(i > 0) sta += dp1[i-1];
if(kraj < n-1) sta += dp2[kraj+1];
sol2 = min(sta,sol2);
}
}
return min(sol1,sol2);
}
ll delivery(int br1,int br2,int br3,int *positions){
n = br1;
k = br2;
l = br3;
for(int i = 0; i < n; i++) pos[i] = positions[i];
int sta = 0;
while(sta < n && pos[sta] == 0) sta++;
if(sta == n) return 0;
for(int i = 0; i < n-sta; i++) pos[i] = pos[i+sta];
n -= sta;
if(k == 1) return kje1();
if(k >= n) return kjen();
return nesto();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
216 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
216 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
216 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
56 ms |
23748 KB |
Output is correct |
34 |
Correct |
24 ms |
22556 KB |
Output is correct |
35 |
Correct |
27 ms |
25412 KB |
Output is correct |
36 |
Correct |
59 ms |
33528 KB |
Output is correct |
37 |
Correct |
63 ms |
33576 KB |
Output is correct |
38 |
Correct |
59 ms |
33548 KB |
Output is correct |
39 |
Correct |
55 ms |
32048 KB |
Output is correct |
40 |
Correct |
33 ms |
27408 KB |
Output is correct |
41 |
Correct |
64 ms |
33532 KB |
Output is correct |
42 |
Correct |
33 ms |
27716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
216 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
56 ms |
23748 KB |
Output is correct |
34 |
Correct |
24 ms |
22556 KB |
Output is correct |
35 |
Correct |
27 ms |
25412 KB |
Output is correct |
36 |
Correct |
59 ms |
33528 KB |
Output is correct |
37 |
Correct |
63 ms |
33576 KB |
Output is correct |
38 |
Correct |
59 ms |
33548 KB |
Output is correct |
39 |
Correct |
55 ms |
32048 KB |
Output is correct |
40 |
Correct |
33 ms |
27408 KB |
Output is correct |
41 |
Correct |
64 ms |
33532 KB |
Output is correct |
42 |
Correct |
33 ms |
27716 KB |
Output is correct |
43 |
Correct |
619 ms |
331964 KB |
Output is correct |
44 |
Correct |
234 ms |
223368 KB |
Output is correct |
45 |
Correct |
289 ms |
259496 KB |
Output is correct |
46 |
Correct |
603 ms |
333012 KB |
Output is correct |
47 |
Correct |
599 ms |
332920 KB |
Output is correct |
48 |
Correct |
600 ms |
332948 KB |
Output is correct |
49 |
Correct |
541 ms |
317724 KB |
Output is correct |
50 |
Correct |
344 ms |
271156 KB |
Output is correct |
51 |
Correct |
603 ms |
332972 KB |
Output is correct |
52 |
Correct |
346 ms |
274284 KB |
Output is correct |