# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70465 | 2018-08-23T02:22:39 Z | Diuven | None (JOI16_ho_t1) | C++14 | 139 ms | 5616 KB |
#include <cstdio> typedef long long ll; const int inf=2e9; const ll linf=2e18; ll min(ll a, ll b){ return a<b ? a : b; } ll max(ll a, ll b){ return a>b ? a : b; } int n, m, k, A[20010]; ll D[20010]; ll d(int i){ if(D[i]>=0) return D[i]; D[i]=linf; for(int s=1, a=-inf, b=inf; s<=m; s++){ if(i<s) break; a=max(a, A[i-s+1]), b=min(b, A[i-s+1]); D[i]=min(D[i], d(i-s)+k+s*ll(a-b)); } return D[i]; } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=n; i++) scanf("%d", A+i); for(int i=1; i<=n; i++) D[i]=-1; D[0]=0; printf("%lld\n", d(n)); return 0; }
Compilation message
# | 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 | 436 KB | Output is correct |
4 | Correct | 2 ms | 488 KB | Output is correct |
5 | Correct | 2 ms | 492 KB | Output is correct |
6 | Correct | 3 ms | 548 KB | Output is correct |
7 | Correct | 2 ms | 580 KB | Output is correct |
8 | Correct | 2 ms | 588 KB | Output is correct |
9 | Correct | 3 ms | 588 KB | Output is correct |
10 | Correct | 2 ms | 664 KB | Output is correct |
11 | Correct | 2 ms | 700 KB | Output is correct |
12 | Correct | 2 ms | 724 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 2 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 884 KB | Output is correct |
2 | Correct | 4 ms | 924 KB | Output is correct |
3 | Correct | 4 ms | 960 KB | Output is correct |
4 | Correct | 4 ms | 996 KB | Output is correct |
5 | Correct | 3 ms | 996 KB | Output is correct |
6 | Correct | 5 ms | 1080 KB | Output is correct |
7 | Correct | 4 ms | 1080 KB | Output is correct |
8 | Correct | 5 ms | 1092 KB | Output is correct |
9 | Correct | 4 ms | 1108 KB | Output is correct |
10 | Correct | 6 ms | 1148 KB | Output is correct |
11 | Correct | 4 ms | 1204 KB | Output is correct |
12 | Correct | 4 ms | 1204 KB | Output is correct |
13 | Correct | 4 ms | 1204 KB | Output is correct |
14 | Correct | 3 ms | 1216 KB | Output is correct |
15 | Correct | 4 ms | 1364 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 | 436 KB | Output is correct |
4 | Correct | 2 ms | 488 KB | Output is correct |
5 | Correct | 2 ms | 492 KB | Output is correct |
6 | Correct | 3 ms | 548 KB | Output is correct |
7 | Correct | 2 ms | 580 KB | Output is correct |
8 | Correct | 2 ms | 588 KB | Output is correct |
9 | Correct | 3 ms | 588 KB | Output is correct |
10 | Correct | 2 ms | 664 KB | Output is correct |
11 | Correct | 2 ms | 700 KB | Output is correct |
12 | Correct | 2 ms | 724 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 2 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
16 | Correct | 3 ms | 884 KB | Output is correct |
17 | Correct | 4 ms | 924 KB | Output is correct |
18 | Correct | 4 ms | 960 KB | Output is correct |
19 | Correct | 4 ms | 996 KB | Output is correct |
20 | Correct | 3 ms | 996 KB | Output is correct |
21 | Correct | 5 ms | 1080 KB | Output is correct |
22 | Correct | 4 ms | 1080 KB | Output is correct |
23 | Correct | 5 ms | 1092 KB | Output is correct |
24 | Correct | 4 ms | 1108 KB | Output is correct |
25 | Correct | 6 ms | 1148 KB | Output is correct |
26 | Correct | 4 ms | 1204 KB | Output is correct |
27 | Correct | 4 ms | 1204 KB | Output is correct |
28 | Correct | 4 ms | 1204 KB | Output is correct |
29 | Correct | 3 ms | 1216 KB | Output is correct |
30 | Correct | 4 ms | 1364 KB | Output is correct |
31 | Correct | 53 ms | 3092 KB | Output is correct |
32 | Correct | 57 ms | 3248 KB | Output is correct |
33 | Correct | 103 ms | 3484 KB | Output is correct |
34 | Correct | 130 ms | 3640 KB | Output is correct |
35 | Correct | 59 ms | 3836 KB | Output is correct |
36 | Correct | 103 ms | 4160 KB | Output is correct |
37 | Correct | 131 ms | 4356 KB | Output is correct |
38 | Correct | 139 ms | 4552 KB | Output is correct |
39 | Correct | 110 ms | 4656 KB | Output is correct |
40 | Correct | 102 ms | 4820 KB | Output is correct |
41 | Correct | 99 ms | 4980 KB | Output is correct |
42 | Correct | 99 ms | 5128 KB | Output is correct |
43 | Correct | 61 ms | 5388 KB | Output is correct |
44 | Correct | 85 ms | 5428 KB | Output is correct |
45 | Correct | 68 ms | 5616 KB | Output is correct |