#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
const int nmax = 200005;
long long n, m, dp[nmax], sum[nmax];
set<long long>s[2];
vector<pair<long long,long long>>vecc;
long long min_total_length(vector<int> r, vector<int> b){
n = (int)r.size();
m = (int)b.size();
for(int i=0;i<n;i++){
s[0].insert(r[i]);
vecc.push_back({r[i], 0});
}
for(int i=0;i<m;i++){
s[1].insert(b[i]);
vecc.push_back({b[i], 1});
}
sort(all(vecc));
for(int i=0;i<(int)vecc.size();i++){
sum[i+1] = sum[i] + vecc[i].fr;
}
int sz_last = 0, sz_curr = 0;
for(int i=0;i<n+m;i++){
dp[i+1] = 1e18;
// case 1
auto it = s[vecc[i].sc ^ 1].lower_bound(vecc[i].fr);
if(it != s[vecc[i].sc^1].begin()){
--it;
if(vecc[i].sc == vecc[i-1].sc) dp[i+1]=min(dp[i+1], dp[i]+vecc[i].fr-(*it));
else{
dp[i+1]=min(dp[i+1],dp[i-1]+vecc[i].fr-(*it));
}
it++;
}
// case 2
if(i > 0){
if(vecc[i].sc != vecc[i-1].sc){
sz_last = sz_curr;
sz_curr = 0;
}
}
sz_curr++;
if(sz_curr <= sz_last){
int indx = i - sz_curr - sz_curr + 1;
dp[i+1]=min(dp[i+1], dp[indx]+sum[i+1]-sum[i+1-sz_curr]-(sum[i+1-sz_curr]-sum[i+1-sz_curr-sz_curr]));
}
// case 3
if(it != s[vecc[i].sc^1].end()){
dp[i+1]=min(dp[i+1],dp[i]+(*it)-vecc[i].fr);
}
}
return dp[n+m];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
78 ms |
13180 KB |
Output is correct |
4 |
Correct |
79 ms |
14656 KB |
Output is correct |
5 |
Correct |
94 ms |
14700 KB |
Output is correct |
6 |
Correct |
115 ms |
19092 KB |
Output is correct |
7 |
Correct |
113 ms |
19236 KB |
Output is correct |
8 |
Correct |
115 ms |
19104 KB |
Output is correct |
9 |
Correct |
114 ms |
19184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
216 KB |
Output is correct |
3 |
Correct |
127 ms |
17452 KB |
Output is correct |
4 |
Correct |
122 ms |
17712 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 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 |
126 ms |
17452 KB |
Output is correct |
19 |
Correct |
123 ms |
17448 KB |
Output is correct |
20 |
Correct |
130 ms |
17452 KB |
Output is correct |
21 |
Correct |
124 ms |
17464 KB |
Output is correct |
22 |
Correct |
121 ms |
17396 KB |
Output is correct |
23 |
Correct |
130 ms |
17456 KB |
Output is correct |
24 |
Correct |
126 ms |
17448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
107 ms |
17452 KB |
Output is correct |
3 |
Correct |
117 ms |
17452 KB |
Output is correct |
4 |
Correct |
113 ms |
17436 KB |
Output is correct |
5 |
Correct |
117 ms |
17456 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 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 |
204 KB |
Output is correct |
11 |
Correct |
0 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 |
110 ms |
17592 KB |
Output is correct |
19 |
Correct |
109 ms |
18732 KB |
Output is correct |
20 |
Correct |
107 ms |
18732 KB |
Output is correct |
21 |
Correct |
106 ms |
18708 KB |
Output is correct |
22 |
Correct |
108 ms |
18716 KB |
Output is correct |
23 |
Correct |
113 ms |
18772 KB |
Output is correct |
24 |
Correct |
103 ms |
18780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 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 |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
78 ms |
13180 KB |
Output is correct |
20 |
Correct |
79 ms |
14656 KB |
Output is correct |
21 |
Correct |
94 ms |
14700 KB |
Output is correct |
22 |
Correct |
115 ms |
19092 KB |
Output is correct |
23 |
Correct |
113 ms |
19236 KB |
Output is correct |
24 |
Correct |
115 ms |
19104 KB |
Output is correct |
25 |
Correct |
114 ms |
19184 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
0 ms |
216 KB |
Output is correct |
28 |
Correct |
127 ms |
17452 KB |
Output is correct |
29 |
Correct |
122 ms |
17712 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
204 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
126 ms |
17452 KB |
Output is correct |
44 |
Correct |
123 ms |
17448 KB |
Output is correct |
45 |
Correct |
130 ms |
17452 KB |
Output is correct |
46 |
Correct |
124 ms |
17464 KB |
Output is correct |
47 |
Correct |
121 ms |
17396 KB |
Output is correct |
48 |
Correct |
130 ms |
17456 KB |
Output is correct |
49 |
Correct |
126 ms |
17448 KB |
Output is correct |
50 |
Correct |
1 ms |
204 KB |
Output is correct |
51 |
Correct |
107 ms |
17452 KB |
Output is correct |
52 |
Correct |
117 ms |
17452 KB |
Output is correct |
53 |
Correct |
113 ms |
17436 KB |
Output is correct |
54 |
Correct |
117 ms |
17456 KB |
Output is correct |
55 |
Correct |
1 ms |
204 KB |
Output is correct |
56 |
Correct |
0 ms |
204 KB |
Output is correct |
57 |
Correct |
1 ms |
204 KB |
Output is correct |
58 |
Correct |
1 ms |
204 KB |
Output is correct |
59 |
Correct |
1 ms |
204 KB |
Output is correct |
60 |
Correct |
0 ms |
204 KB |
Output is correct |
61 |
Correct |
1 ms |
204 KB |
Output is correct |
62 |
Correct |
1 ms |
204 KB |
Output is correct |
63 |
Correct |
1 ms |
204 KB |
Output is correct |
64 |
Correct |
1 ms |
204 KB |
Output is correct |
65 |
Correct |
1 ms |
204 KB |
Output is correct |
66 |
Correct |
1 ms |
204 KB |
Output is correct |
67 |
Correct |
110 ms |
17592 KB |
Output is correct |
68 |
Correct |
109 ms |
18732 KB |
Output is correct |
69 |
Correct |
107 ms |
18732 KB |
Output is correct |
70 |
Correct |
106 ms |
18708 KB |
Output is correct |
71 |
Correct |
108 ms |
18716 KB |
Output is correct |
72 |
Correct |
113 ms |
18772 KB |
Output is correct |
73 |
Correct |
103 ms |
18780 KB |
Output is correct |
74 |
Correct |
106 ms |
19180 KB |
Output is correct |
75 |
Correct |
112 ms |
18964 KB |
Output is correct |
76 |
Correct |
111 ms |
19116 KB |
Output is correct |
77 |
Correct |
114 ms |
19028 KB |
Output is correct |
78 |
Correct |
107 ms |
18784 KB |
Output is correct |
79 |
Correct |
116 ms |
18860 KB |
Output is correct |
80 |
Correct |
108 ms |
18828 KB |
Output is correct |
81 |
Correct |
114 ms |
18844 KB |
Output is correct |
82 |
Correct |
106 ms |
18836 KB |
Output is correct |
83 |
Correct |
110 ms |
18972 KB |
Output is correct |
84 |
Correct |
113 ms |
19092 KB |
Output is correct |
85 |
Correct |
119 ms |
19084 KB |
Output is correct |
86 |
Correct |
110 ms |
19168 KB |
Output is correct |
87 |
Correct |
109 ms |
19116 KB |
Output is correct |
88 |
Correct |
113 ms |
19212 KB |
Output is correct |
89 |
Correct |
106 ms |
19168 KB |
Output is correct |
90 |
Correct |
117 ms |
19116 KB |
Output is correct |
91 |
Correct |
104 ms |
19096 KB |
Output is correct |
92 |
Correct |
108 ms |
19088 KB |
Output is correct |
93 |
Correct |
105 ms |
19152 KB |
Output is correct |
94 |
Correct |
116 ms |
19136 KB |
Output is correct |
95 |
Correct |
112 ms |
19116 KB |
Output is correct |
96 |
Correct |
107 ms |
19256 KB |
Output is correct |
97 |
Correct |
110 ms |
19116 KB |
Output is correct |
98 |
Correct |
109 ms |
19084 KB |
Output is correct |
99 |
Correct |
109 ms |
19116 KB |
Output is correct |
100 |
Correct |
115 ms |
19108 KB |
Output is correct |
101 |
Correct |
107 ms |
19096 KB |
Output is correct |
102 |
Correct |
120 ms |
19112 KB |
Output is correct |