#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,avx,avx2,popcnt,lzcnt,abm,bmi,bmi2")
// #pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,tune=native,popcnt,lzcnt,abm,bmi,bmi2")
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((ll)(a).size())
using ll = long long;
const ll infll = (ll)1e18 + 7;
const int N = 2e5 + 5;
struct line_container{
struct line_type{
ll a, b;
mutable ll p;
bool operator< (const line_type& oth) const{
return a < oth.a;
}
bool operator< (ll x) const{
return p < x;
}
};
multiset <line_type, less<>> mts;
const ll inf = infll;
ll div(ll x, ll y){
return x / y - ((x ^ y) < 0 and x % y);
}
template <class T>
bool isect(T x, T y){
if (y == mts.end()){
x->p = infll;
return false;
}
if (x->a == y->a){
x->p = x->b > y->b ? infll : -infll;
}
else{
x->p = div(y->b - x->b, x->a - y->a);
}
return x->p >= y->p;
}
void insert(line_type l){
l.a = -l.a; l.b = -l.b;
auto z = mts.insert(mts.end(), l), y = z++, x = y;
while (isect(y, z)){
z = mts.erase(z);
}
if (x != mts.begin() and isect(--x, y)){
isect(x, mts.erase(y));
}
while ((y = x) != mts.begin() and (--x)->p >= y->p){
isect(x, mts.erase(y));
}
}
ll query(ll x){
if (mts.empty()){
return infll;
}
auto l = *mts.lower_bound(x);
return -(l.a * x + l.b);
}
};
int n, m;
int a[N];
bool col[N];
pair <int, int> pre[N][2];
ll pref[N];
ll dp[N];
line_container seg[1 << 19];
void update(int id, int l, int r, int i, const line_container::line_type& ln){
seg[id].insert(ln);
if (l == r){
return;
}
int mid = (l + r) >> 1;
if (i <= mid){
update(id * 2, l, mid, i, ln);
}
else{
update(id * 2 + 1, mid + 1, r, i, ln);
}
}
ll query(int id, int l, int r, int u, int v, ll x){
if (v < l or r < u){
return infll;
}
if (u <= l and r <= v){
return seg[id].query(x);
}
int mid = (l + r) >> 1;
return min(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x));
}
void update_dp(int i){
update(1, 0, n + m, i, line_container::line_type{i, dp[i] + pref[i]});
}
ll min_total_length(vector <int> r, vector <int> b){
n = isz(r);
m = isz(b);
{
int i = 0, j = 0;
while (i < n or j < m){
if (j == m){
a[i + j + 1] = r[i];
col[i + j + 1] = true;
i++;
}
else if (i == n){
a[i + j + 1] = b[j];
col[i + j + 1] = false;
j++;
}
else if (r[i] < b[j]){
a[i + j + 1] = r[i];
col[i + j + 1] = true;
i++;
}
else{
a[i + j + 1] = b[j];
col[i + j + 1] = false;
j++;
}
}
}
pre[0][0] = pair{0, 0};
pre[0][1] = pair{0, 0};
ForE(i, 1, n + m){
pre[i][0] = pre[i - 1][0];
pre[i][1] = pre[i - 1][1];
swap(pre[i][col[i]].fi, pre[i][col[i]].se);
pre[i][col[i]].fi = i;
}
pref[0] = 0;
ForE(i, 1, n + m){
pref[i] = pref[i - 1] + a[i];
}
fill(dp, dp + n + m + 1, infll);
dp[0] = 0;
update_dp(0);
ForE(i, 1, n + m){
if (pre[i][0].fi == 0 or pre[i][1].fi == 0){
continue;
}
int j = pre[i][col[i] ^ 1].fi;
dp[i] = min(dp[i], a[i] - a[j] + dp[i - 1]);
int k = pre[j][col[i]].fi;
int leni = i - j, lenj = j - k;
if (leni <= lenj){
ll sum = (pref[i] - pref[j]) - (pref[j] - pref[j - leni]);
int r = j - leni, l = k;
// cout << l << ' ' << r << ' ' << query(1, 0, n + m, l, r, -(j + 1)) << endl;
dp[i] = min(dp[i], sum + (ll)r * a[j + 1] - pref[r] + query(1, 0, n + m, l, r, -a[j + 1]));
// for (int x = j - leni; x >= k; x--){
// dp[i] = min(dp[i], sum + dp[x]);
// sum += (j + 1) - x;
// }
}
// cout << "dp " << i << ' ' << dp[i] << endl;
update_dp(i);
}
return dp[n + m];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
29012 KB |
Output is correct |
2 |
Correct |
15 ms |
28988 KB |
Output is correct |
3 |
Correct |
15 ms |
29072 KB |
Output is correct |
4 |
Correct |
14 ms |
28972 KB |
Output is correct |
5 |
Correct |
15 ms |
29060 KB |
Output is correct |
6 |
Correct |
16 ms |
28972 KB |
Output is correct |
7 |
Correct |
15 ms |
29244 KB |
Output is correct |
8 |
Correct |
15 ms |
29200 KB |
Output is correct |
9 |
Correct |
15 ms |
29204 KB |
Output is correct |
10 |
Correct |
15 ms |
29140 KB |
Output is correct |
11 |
Correct |
17 ms |
29204 KB |
Output is correct |
12 |
Correct |
15 ms |
29268 KB |
Output is correct |
13 |
Correct |
15 ms |
29228 KB |
Output is correct |
14 |
Correct |
15 ms |
29120 KB |
Output is correct |
15 |
Correct |
15 ms |
29140 KB |
Output is correct |
16 |
Correct |
16 ms |
29288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
29104 KB |
Output is correct |
2 |
Correct |
15 ms |
29012 KB |
Output is correct |
3 |
Correct |
238 ms |
92820 KB |
Output is correct |
4 |
Correct |
239 ms |
92668 KB |
Output is correct |
5 |
Correct |
437 ms |
149936 KB |
Output is correct |
6 |
Correct |
499 ms |
154828 KB |
Output is correct |
7 |
Correct |
478 ms |
154876 KB |
Output is correct |
8 |
Correct |
470 ms |
154744 KB |
Output is correct |
9 |
Correct |
470 ms |
154792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
29020 KB |
Output is correct |
2 |
Correct |
14 ms |
29012 KB |
Output is correct |
3 |
Correct |
702 ms |
188292 KB |
Output is correct |
4 |
Correct |
694 ms |
184124 KB |
Output is correct |
5 |
Correct |
14 ms |
29012 KB |
Output is correct |
6 |
Correct |
15 ms |
29072 KB |
Output is correct |
7 |
Correct |
14 ms |
29008 KB |
Output is correct |
8 |
Correct |
15 ms |
29012 KB |
Output is correct |
9 |
Correct |
14 ms |
29032 KB |
Output is correct |
10 |
Correct |
15 ms |
29052 KB |
Output is correct |
11 |
Correct |
15 ms |
29040 KB |
Output is correct |
12 |
Correct |
17 ms |
29024 KB |
Output is correct |
13 |
Correct |
14 ms |
29020 KB |
Output is correct |
14 |
Correct |
15 ms |
29012 KB |
Output is correct |
15 |
Correct |
15 ms |
29056 KB |
Output is correct |
16 |
Correct |
14 ms |
29136 KB |
Output is correct |
17 |
Correct |
14 ms |
29064 KB |
Output is correct |
18 |
Correct |
697 ms |
188016 KB |
Output is correct |
19 |
Correct |
689 ms |
187720 KB |
Output is correct |
20 |
Correct |
696 ms |
184308 KB |
Output is correct |
21 |
Correct |
699 ms |
187928 KB |
Output is correct |
22 |
Correct |
717 ms |
186428 KB |
Output is correct |
23 |
Correct |
710 ms |
186696 KB |
Output is correct |
24 |
Correct |
696 ms |
186908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
29064 KB |
Output is correct |
2 |
Correct |
847 ms |
229504 KB |
Output is correct |
3 |
Correct |
704 ms |
181360 KB |
Output is correct |
4 |
Correct |
780 ms |
212400 KB |
Output is correct |
5 |
Correct |
684 ms |
181320 KB |
Output is correct |
6 |
Correct |
18 ms |
29036 KB |
Output is correct |
7 |
Correct |
15 ms |
29036 KB |
Output is correct |
8 |
Correct |
15 ms |
28944 KB |
Output is correct |
9 |
Correct |
17 ms |
28988 KB |
Output is correct |
10 |
Correct |
18 ms |
29028 KB |
Output is correct |
11 |
Correct |
15 ms |
29004 KB |
Output is correct |
12 |
Correct |
14 ms |
29052 KB |
Output is correct |
13 |
Correct |
14 ms |
28952 KB |
Output is correct |
14 |
Correct |
15 ms |
29012 KB |
Output is correct |
15 |
Correct |
14 ms |
29140 KB |
Output is correct |
16 |
Correct |
15 ms |
29120 KB |
Output is correct |
17 |
Correct |
15 ms |
29012 KB |
Output is correct |
18 |
Correct |
802 ms |
206548 KB |
Output is correct |
19 |
Correct |
792 ms |
208012 KB |
Output is correct |
20 |
Correct |
835 ms |
217900 KB |
Output is correct |
21 |
Correct |
869 ms |
223664 KB |
Output is correct |
22 |
Correct |
701 ms |
191932 KB |
Output is correct |
23 |
Correct |
533 ms |
161684 KB |
Output is correct |
24 |
Correct |
670 ms |
184568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
29012 KB |
Output is correct |
2 |
Correct |
15 ms |
28988 KB |
Output is correct |
3 |
Correct |
15 ms |
29072 KB |
Output is correct |
4 |
Correct |
14 ms |
28972 KB |
Output is correct |
5 |
Correct |
15 ms |
29060 KB |
Output is correct |
6 |
Correct |
16 ms |
28972 KB |
Output is correct |
7 |
Correct |
15 ms |
29244 KB |
Output is correct |
8 |
Correct |
15 ms |
29200 KB |
Output is correct |
9 |
Correct |
15 ms |
29204 KB |
Output is correct |
10 |
Correct |
15 ms |
29140 KB |
Output is correct |
11 |
Correct |
17 ms |
29204 KB |
Output is correct |
12 |
Correct |
15 ms |
29268 KB |
Output is correct |
13 |
Correct |
15 ms |
29228 KB |
Output is correct |
14 |
Correct |
15 ms |
29120 KB |
Output is correct |
15 |
Correct |
15 ms |
29140 KB |
Output is correct |
16 |
Correct |
16 ms |
29288 KB |
Output is correct |
17 |
Correct |
17 ms |
29104 KB |
Output is correct |
18 |
Correct |
15 ms |
29012 KB |
Output is correct |
19 |
Correct |
238 ms |
92820 KB |
Output is correct |
20 |
Correct |
239 ms |
92668 KB |
Output is correct |
21 |
Correct |
437 ms |
149936 KB |
Output is correct |
22 |
Correct |
499 ms |
154828 KB |
Output is correct |
23 |
Correct |
478 ms |
154876 KB |
Output is correct |
24 |
Correct |
470 ms |
154744 KB |
Output is correct |
25 |
Correct |
470 ms |
154792 KB |
Output is correct |
26 |
Correct |
14 ms |
29020 KB |
Output is correct |
27 |
Correct |
14 ms |
29012 KB |
Output is correct |
28 |
Correct |
702 ms |
188292 KB |
Output is correct |
29 |
Correct |
694 ms |
184124 KB |
Output is correct |
30 |
Correct |
14 ms |
29012 KB |
Output is correct |
31 |
Correct |
15 ms |
29072 KB |
Output is correct |
32 |
Correct |
14 ms |
29008 KB |
Output is correct |
33 |
Correct |
15 ms |
29012 KB |
Output is correct |
34 |
Correct |
14 ms |
29032 KB |
Output is correct |
35 |
Correct |
15 ms |
29052 KB |
Output is correct |
36 |
Correct |
15 ms |
29040 KB |
Output is correct |
37 |
Correct |
17 ms |
29024 KB |
Output is correct |
38 |
Correct |
14 ms |
29020 KB |
Output is correct |
39 |
Correct |
15 ms |
29012 KB |
Output is correct |
40 |
Correct |
15 ms |
29056 KB |
Output is correct |
41 |
Correct |
14 ms |
29136 KB |
Output is correct |
42 |
Correct |
14 ms |
29064 KB |
Output is correct |
43 |
Correct |
697 ms |
188016 KB |
Output is correct |
44 |
Correct |
689 ms |
187720 KB |
Output is correct |
45 |
Correct |
696 ms |
184308 KB |
Output is correct |
46 |
Correct |
699 ms |
187928 KB |
Output is correct |
47 |
Correct |
717 ms |
186428 KB |
Output is correct |
48 |
Correct |
710 ms |
186696 KB |
Output is correct |
49 |
Correct |
696 ms |
186908 KB |
Output is correct |
50 |
Correct |
15 ms |
29064 KB |
Output is correct |
51 |
Correct |
847 ms |
229504 KB |
Output is correct |
52 |
Correct |
704 ms |
181360 KB |
Output is correct |
53 |
Correct |
780 ms |
212400 KB |
Output is correct |
54 |
Correct |
684 ms |
181320 KB |
Output is correct |
55 |
Correct |
18 ms |
29036 KB |
Output is correct |
56 |
Correct |
15 ms |
29036 KB |
Output is correct |
57 |
Correct |
15 ms |
28944 KB |
Output is correct |
58 |
Correct |
17 ms |
28988 KB |
Output is correct |
59 |
Correct |
18 ms |
29028 KB |
Output is correct |
60 |
Correct |
15 ms |
29004 KB |
Output is correct |
61 |
Correct |
14 ms |
29052 KB |
Output is correct |
62 |
Correct |
14 ms |
28952 KB |
Output is correct |
63 |
Correct |
15 ms |
29012 KB |
Output is correct |
64 |
Correct |
14 ms |
29140 KB |
Output is correct |
65 |
Correct |
15 ms |
29120 KB |
Output is correct |
66 |
Correct |
15 ms |
29012 KB |
Output is correct |
67 |
Correct |
802 ms |
206548 KB |
Output is correct |
68 |
Correct |
792 ms |
208012 KB |
Output is correct |
69 |
Correct |
835 ms |
217900 KB |
Output is correct |
70 |
Correct |
869 ms |
223664 KB |
Output is correct |
71 |
Correct |
701 ms |
191932 KB |
Output is correct |
72 |
Correct |
533 ms |
161684 KB |
Output is correct |
73 |
Correct |
670 ms |
184568 KB |
Output is correct |
74 |
Correct |
528 ms |
157380 KB |
Output is correct |
75 |
Correct |
686 ms |
197628 KB |
Output is correct |
76 |
Correct |
618 ms |
175572 KB |
Output is correct |
77 |
Correct |
872 ms |
227000 KB |
Output is correct |
78 |
Correct |
691 ms |
190244 KB |
Output is correct |
79 |
Correct |
868 ms |
235676 KB |
Output is correct |
80 |
Correct |
604 ms |
174436 KB |
Output is correct |
81 |
Correct |
502 ms |
163800 KB |
Output is correct |
82 |
Correct |
481 ms |
155432 KB |
Output is correct |
83 |
Correct |
560 ms |
171900 KB |
Output is correct |
84 |
Correct |
485 ms |
155208 KB |
Output is correct |
85 |
Correct |
786 ms |
213284 KB |
Output is correct |
86 |
Correct |
711 ms |
185512 KB |
Output is correct |
87 |
Correct |
621 ms |
180704 KB |
Output is correct |
88 |
Correct |
654 ms |
182396 KB |
Output is correct |
89 |
Correct |
667 ms |
186832 KB |
Output is correct |
90 |
Correct |
774 ms |
209388 KB |
Output is correct |
91 |
Correct |
521 ms |
156956 KB |
Output is correct |
92 |
Correct |
802 ms |
208612 KB |
Output is correct |
93 |
Correct |
607 ms |
172660 KB |
Output is correct |
94 |
Correct |
835 ms |
235752 KB |
Output is correct |
95 |
Correct |
875 ms |
226412 KB |
Output is correct |
96 |
Correct |
574 ms |
169980 KB |
Output is correct |
97 |
Correct |
530 ms |
162660 KB |
Output is correct |
98 |
Correct |
657 ms |
188572 KB |
Output is correct |
99 |
Correct |
679 ms |
188636 KB |
Output is correct |
100 |
Correct |
901 ms |
240388 KB |
Output is correct |
101 |
Correct |
530 ms |
161844 KB |
Output is correct |
102 |
Correct |
607 ms |
170756 KB |
Output is correct |