#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
const ll inf = 1e18 + 1;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
pair < ll , int > T[N];
ll L[N], R[N], dp[N], p[N];
ll bld(ll l, ll r, ll x, ll y){
ll sz = 1;
ll p = 0;
for(ll i = r; i >= l; i--, sz++){
p += T[i].st;
L[sz] = min(dp[i], dp[i - 1]) - p + sz * x;
R[sz] = min(dp[i], dp[i - 1]) - p + sz * y;
}
assert(L[sz] > mod && R[sz] > mod);
return sz - 1;
}
ll min_total_length(vector < int > a, vector < int > b){
int n = a.size();
int m = b.size();
int t = 0;
for(int i = 0, j = 0; i < n || j < m ;){
if(j == m || (i < n && a[i] < b[j])) T[++t] = mp(a[i++], 1);
else T[++t] = mp(b[j++], 2);
}
memset(L, 22, sizeof L);
memset(R, 22, sizeof R);
int l = 1;
int r = 1;
for(; T[r].nd == T[r + 1].nd; r++)
dp[r] = inf;
dp[r] = inf;
for(int i = r + 1; i <= t; i = r + 1){
int j = i;
for(; T[j].nd == T[j + 1].nd; j++);
int x = T[i].st;
int y = T[i - 1].st;
ll psz = bld(l, r, x, y);
ll mn = inf;
ll sz = 1;
for(int k = i; k <= j; k++, sz++){
p[sz] = p[sz - 1] + T[k].st;
mn = min(mn, R[sz]);
dp[k] = mn + p[sz] - sz * y;
}
mn = inf;
sz = j - i + 1;
for(; psz > sz; psz--) mn = min(mn, L[psz]);
for(int k = j; k >= i; k--, sz--){
mn = min(mn, L[sz]);
dp[k] = min(dp[k], mn + p[sz] - sz * x);
}
for(int k = 1; k <= r - l + 1; k++)
L[k] = R[k] = inf;
l = i;
r = j;
}
return dp[t];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3404 KB |
Output is correct |
2 |
Correct |
1 ms |
3404 KB |
Output is correct |
3 |
Correct |
2 ms |
3404 KB |
Output is correct |
4 |
Correct |
2 ms |
3404 KB |
Output is correct |
5 |
Correct |
1 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
1 ms |
3404 KB |
Output is correct |
8 |
Correct |
2 ms |
3376 KB |
Output is correct |
9 |
Correct |
1 ms |
3404 KB |
Output is correct |
10 |
Correct |
2 ms |
3372 KB |
Output is correct |
11 |
Correct |
1 ms |
3368 KB |
Output is correct |
12 |
Correct |
2 ms |
3404 KB |
Output is correct |
13 |
Correct |
2 ms |
3404 KB |
Output is correct |
14 |
Correct |
1 ms |
3404 KB |
Output is correct |
15 |
Correct |
2 ms |
3404 KB |
Output is correct |
16 |
Correct |
2 ms |
3404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
Output is correct |
2 |
Correct |
2 ms |
3404 KB |
Output is correct |
3 |
Correct |
22 ms |
9960 KB |
Output is correct |
4 |
Correct |
19 ms |
9952 KB |
Output is correct |
5 |
Correct |
20 ms |
10316 KB |
Output is correct |
6 |
Correct |
26 ms |
12348 KB |
Output is correct |
7 |
Correct |
25 ms |
12336 KB |
Output is correct |
8 |
Correct |
25 ms |
12364 KB |
Output is correct |
9 |
Correct |
24 ms |
12344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
Output is correct |
2 |
Correct |
2 ms |
3368 KB |
Output is correct |
3 |
Correct |
29 ms |
11588 KB |
Output is correct |
4 |
Correct |
28 ms |
11184 KB |
Output is correct |
5 |
Correct |
2 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
3404 KB |
Output is correct |
9 |
Correct |
1 ms |
3404 KB |
Output is correct |
10 |
Correct |
2 ms |
3404 KB |
Output is correct |
11 |
Correct |
2 ms |
3376 KB |
Output is correct |
12 |
Correct |
1 ms |
3404 KB |
Output is correct |
13 |
Correct |
2 ms |
3404 KB |
Output is correct |
14 |
Correct |
2 ms |
3404 KB |
Output is correct |
15 |
Correct |
2 ms |
3404 KB |
Output is correct |
16 |
Correct |
2 ms |
3404 KB |
Output is correct |
17 |
Correct |
1 ms |
3404 KB |
Output is correct |
18 |
Correct |
35 ms |
11556 KB |
Output is correct |
19 |
Correct |
26 ms |
11596 KB |
Output is correct |
20 |
Correct |
29 ms |
11592 KB |
Output is correct |
21 |
Correct |
30 ms |
11596 KB |
Output is correct |
22 |
Correct |
27 ms |
11576 KB |
Output is correct |
23 |
Correct |
26 ms |
11572 KB |
Output is correct |
24 |
Correct |
26 ms |
11568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3404 KB |
Output is correct |
2 |
Correct |
21 ms |
10936 KB |
Output is correct |
3 |
Correct |
24 ms |
10928 KB |
Output is correct |
4 |
Correct |
22 ms |
10976 KB |
Output is correct |
5 |
Correct |
22 ms |
10948 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
3404 KB |
Output is correct |
9 |
Correct |
1 ms |
3368 KB |
Output is correct |
10 |
Correct |
2 ms |
3404 KB |
Output is correct |
11 |
Correct |
1 ms |
3404 KB |
Output is correct |
12 |
Correct |
2 ms |
3404 KB |
Output is correct |
13 |
Correct |
1 ms |
3404 KB |
Output is correct |
14 |
Correct |
1 ms |
3368 KB |
Output is correct |
15 |
Correct |
2 ms |
3404 KB |
Output is correct |
16 |
Correct |
2 ms |
3404 KB |
Output is correct |
17 |
Correct |
2 ms |
3404 KB |
Output is correct |
18 |
Correct |
25 ms |
11180 KB |
Output is correct |
19 |
Correct |
22 ms |
10936 KB |
Output is correct |
20 |
Correct |
21 ms |
10928 KB |
Output is correct |
21 |
Correct |
21 ms |
11056 KB |
Output is correct |
22 |
Correct |
22 ms |
11596 KB |
Output is correct |
23 |
Correct |
22 ms |
11436 KB |
Output is correct |
24 |
Correct |
20 ms |
11436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3404 KB |
Output is correct |
2 |
Correct |
1 ms |
3404 KB |
Output is correct |
3 |
Correct |
2 ms |
3404 KB |
Output is correct |
4 |
Correct |
2 ms |
3404 KB |
Output is correct |
5 |
Correct |
1 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
1 ms |
3404 KB |
Output is correct |
8 |
Correct |
2 ms |
3376 KB |
Output is correct |
9 |
Correct |
1 ms |
3404 KB |
Output is correct |
10 |
Correct |
2 ms |
3372 KB |
Output is correct |
11 |
Correct |
1 ms |
3368 KB |
Output is correct |
12 |
Correct |
2 ms |
3404 KB |
Output is correct |
13 |
Correct |
2 ms |
3404 KB |
Output is correct |
14 |
Correct |
1 ms |
3404 KB |
Output is correct |
15 |
Correct |
2 ms |
3404 KB |
Output is correct |
16 |
Correct |
2 ms |
3404 KB |
Output is correct |
17 |
Correct |
2 ms |
3404 KB |
Output is correct |
18 |
Correct |
2 ms |
3404 KB |
Output is correct |
19 |
Correct |
22 ms |
9960 KB |
Output is correct |
20 |
Correct |
19 ms |
9952 KB |
Output is correct |
21 |
Correct |
20 ms |
10316 KB |
Output is correct |
22 |
Correct |
26 ms |
12348 KB |
Output is correct |
23 |
Correct |
25 ms |
12336 KB |
Output is correct |
24 |
Correct |
25 ms |
12364 KB |
Output is correct |
25 |
Correct |
24 ms |
12344 KB |
Output is correct |
26 |
Correct |
2 ms |
3404 KB |
Output is correct |
27 |
Correct |
2 ms |
3368 KB |
Output is correct |
28 |
Correct |
29 ms |
11588 KB |
Output is correct |
29 |
Correct |
28 ms |
11184 KB |
Output is correct |
30 |
Correct |
2 ms |
3404 KB |
Output is correct |
31 |
Correct |
2 ms |
3404 KB |
Output is correct |
32 |
Correct |
2 ms |
3404 KB |
Output is correct |
33 |
Correct |
1 ms |
3404 KB |
Output is correct |
34 |
Correct |
1 ms |
3404 KB |
Output is correct |
35 |
Correct |
2 ms |
3404 KB |
Output is correct |
36 |
Correct |
2 ms |
3376 KB |
Output is correct |
37 |
Correct |
1 ms |
3404 KB |
Output is correct |
38 |
Correct |
2 ms |
3404 KB |
Output is correct |
39 |
Correct |
2 ms |
3404 KB |
Output is correct |
40 |
Correct |
2 ms |
3404 KB |
Output is correct |
41 |
Correct |
2 ms |
3404 KB |
Output is correct |
42 |
Correct |
1 ms |
3404 KB |
Output is correct |
43 |
Correct |
35 ms |
11556 KB |
Output is correct |
44 |
Correct |
26 ms |
11596 KB |
Output is correct |
45 |
Correct |
29 ms |
11592 KB |
Output is correct |
46 |
Correct |
30 ms |
11596 KB |
Output is correct |
47 |
Correct |
27 ms |
11576 KB |
Output is correct |
48 |
Correct |
26 ms |
11572 KB |
Output is correct |
49 |
Correct |
26 ms |
11568 KB |
Output is correct |
50 |
Correct |
1 ms |
3404 KB |
Output is correct |
51 |
Correct |
21 ms |
10936 KB |
Output is correct |
52 |
Correct |
24 ms |
10928 KB |
Output is correct |
53 |
Correct |
22 ms |
10976 KB |
Output is correct |
54 |
Correct |
22 ms |
10948 KB |
Output is correct |
55 |
Correct |
2 ms |
3404 KB |
Output is correct |
56 |
Correct |
2 ms |
3404 KB |
Output is correct |
57 |
Correct |
1 ms |
3404 KB |
Output is correct |
58 |
Correct |
1 ms |
3368 KB |
Output is correct |
59 |
Correct |
2 ms |
3404 KB |
Output is correct |
60 |
Correct |
1 ms |
3404 KB |
Output is correct |
61 |
Correct |
2 ms |
3404 KB |
Output is correct |
62 |
Correct |
1 ms |
3404 KB |
Output is correct |
63 |
Correct |
1 ms |
3368 KB |
Output is correct |
64 |
Correct |
2 ms |
3404 KB |
Output is correct |
65 |
Correct |
2 ms |
3404 KB |
Output is correct |
66 |
Correct |
2 ms |
3404 KB |
Output is correct |
67 |
Correct |
25 ms |
11180 KB |
Output is correct |
68 |
Correct |
22 ms |
10936 KB |
Output is correct |
69 |
Correct |
21 ms |
10928 KB |
Output is correct |
70 |
Correct |
21 ms |
11056 KB |
Output is correct |
71 |
Correct |
22 ms |
11596 KB |
Output is correct |
72 |
Correct |
22 ms |
11436 KB |
Output is correct |
73 |
Correct |
20 ms |
11436 KB |
Output is correct |
74 |
Correct |
25 ms |
12200 KB |
Output is correct |
75 |
Correct |
23 ms |
11572 KB |
Output is correct |
76 |
Correct |
32 ms |
11808 KB |
Output is correct |
77 |
Correct |
21 ms |
11564 KB |
Output is correct |
78 |
Correct |
27 ms |
11560 KB |
Output is correct |
79 |
Correct |
22 ms |
11436 KB |
Output is correct |
80 |
Correct |
34 ms |
11312 KB |
Output is correct |
81 |
Correct |
23 ms |
11692 KB |
Output is correct |
82 |
Correct |
22 ms |
11440 KB |
Output is correct |
83 |
Correct |
23 ms |
11700 KB |
Output is correct |
84 |
Correct |
25 ms |
11948 KB |
Output is correct |
85 |
Correct |
24 ms |
11980 KB |
Output is correct |
86 |
Correct |
25 ms |
12108 KB |
Output is correct |
87 |
Correct |
25 ms |
11944 KB |
Output is correct |
88 |
Correct |
27 ms |
11948 KB |
Output is correct |
89 |
Correct |
27 ms |
12084 KB |
Output is correct |
90 |
Correct |
26 ms |
12020 KB |
Output is correct |
91 |
Correct |
26 ms |
11948 KB |
Output is correct |
92 |
Correct |
24 ms |
12088 KB |
Output is correct |
93 |
Correct |
26 ms |
12100 KB |
Output is correct |
94 |
Correct |
25 ms |
12192 KB |
Output is correct |
95 |
Correct |
25 ms |
11948 KB |
Output is correct |
96 |
Correct |
24 ms |
12020 KB |
Output is correct |
97 |
Correct |
25 ms |
12336 KB |
Output is correct |
98 |
Correct |
25 ms |
12228 KB |
Output is correct |
99 |
Correct |
25 ms |
12324 KB |
Output is correct |
100 |
Correct |
25 ms |
12108 KB |
Output is correct |
101 |
Correct |
25 ms |
12096 KB |
Output is correct |
102 |
Correct |
27 ms |
11988 KB |
Output is correct |