#include <bits/stdc++.h>
#include "wiring.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100,inf=(ll)1e15;
ll dp[N];
ll par[N];
vector <pii> a;
ll solve(ll l,ll r,ll L,ll R){
ll zz=0;
if (l>0) zz=par[l-1];
ll ans=-(par[r]-zz)+par[R]-par[L-1];
ll z=r-l+1;
ll t=R-L+1;
if (z<t){
ans-=(t-z)*a[r].F;
}
else{
ans+=(z-t)*a[L].F;
}
return ans;
}
void devide(ll l,ll r,ll L,ll R,ll k){
if (r<l) return ;
ll mid=(r+l)/2;
ll id=L,mx=inf;
for (int i=L;i<=R;i++){
ll z=solve(mid,k,k+1,i)+min(dp[i],dp[i+1]);
if (z<=mx){
mx=z;
id=i;
}
}
dp[mid]=mx;
devide(mid+1,r,L,id,k);
devide(l,mid-1,id,R,k);
}
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
for (auto u : r){
a.pb({u,0});
}
for (auto u : b){
a.pb({u,1});
}
sort(a.begin(),a.end());
par[0]=a[0].F;
for (int i=1;i<a.size();i++){
par[i]=par[i-1]+a[i].F;
}
memset(dp,63,sizeof dp);
dp[a.size()]=0;
vector <int> best;
for (int i=a.size()-2;i>-1;i--){
ll id=i;
if (i>0 && a[i-1].S==a[i].S) continue;
while(id<a.size() && a[id].S==a[i].S) id++;
if (id==a.size()) continue;
ll id2=id;
while(id2<a.size() && a[id2].S==a[id].S) id2++;
// cout << a[i].F << " " << i << " " << id << " " << id2 << endl;
/*
ll ww=i;
for (int j=id;j<id2;j++){
// cout << i << " " << id-1 << " " << j << " " << solve(i,id-1,id,j) << endl;
dp[i]=min(dp[i],solve(i,id-1,id,j)+min(dp[j],dp[j+1]));
if (dp[i]==solve(i,id-1,id,j)+min(dp[j],dp[j+1])){
ww=j;
}
}
best.pb(ww);
*/
// cout << i << " " << id-1 << " " << id+1 << " " << id2-1 << endl;
devide(i,id-1,id,id2-1,id-1);
// cout << i << " " << dp[i] << endl;
}
return dp[0];
}
/*
int32_t main() {
int32_t n, m;
assert(2 == scanf("%d %d", &n, &m));
vector<int32_t> r(n), b(m);
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &r[i]));
for(int i = 0; i < m; i++)
assert(1 == scanf("%d", &b[i]));
long long res = min_total_length(r, b);
printf("%lld\n", res);
return 0;
}
*/
/*
4 5
1 2 3 7
0 4 5 9 10
*/
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:59:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i=1;i<a.size();i++){
| ~^~~~~~~~~
wiring.cpp:68:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while(id<a.size() && a[id].S==a[i].S) id++;
| ~~^~~~~~~~~
wiring.cpp:69:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if (id==a.size()) continue;
| ~~^~~~~~~~~~
wiring.cpp:71:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while(id2<a.size() && a[id2].S==a[id].S) id2++;
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
1868 KB |
Output is correct |
3 |
Correct |
1 ms |
1868 KB |
Output is correct |
4 |
Correct |
1 ms |
1868 KB |
Output is correct |
5 |
Correct |
1 ms |
1868 KB |
Output is correct |
6 |
Correct |
1 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
1836 KB |
Output is correct |
8 |
Correct |
1 ms |
1868 KB |
Output is correct |
9 |
Correct |
1 ms |
1836 KB |
Output is correct |
10 |
Correct |
1 ms |
1868 KB |
Output is correct |
11 |
Correct |
1 ms |
1872 KB |
Output is correct |
12 |
Correct |
1 ms |
1868 KB |
Output is correct |
13 |
Correct |
1 ms |
1872 KB |
Output is correct |
14 |
Correct |
1 ms |
1868 KB |
Output is correct |
15 |
Correct |
2 ms |
1880 KB |
Output is correct |
16 |
Correct |
1 ms |
1872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1868 KB |
Output is correct |
2 |
Correct |
1 ms |
1868 KB |
Output is correct |
3 |
Correct |
35 ms |
6704 KB |
Output is correct |
4 |
Correct |
33 ms |
7984 KB |
Output is correct |
5 |
Correct |
34 ms |
8012 KB |
Output is correct |
6 |
Correct |
45 ms |
9540 KB |
Output is correct |
7 |
Correct |
45 ms |
9520 KB |
Output is correct |
8 |
Correct |
44 ms |
9520 KB |
Output is correct |
9 |
Correct |
44 ms |
9536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
1 ms |
1868 KB |
Output is correct |
3 |
Correct |
57 ms |
8308 KB |
Output is correct |
4 |
Correct |
56 ms |
8368 KB |
Output is correct |
5 |
Correct |
1 ms |
1836 KB |
Output is correct |
6 |
Correct |
1 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
1872 KB |
Output is correct |
8 |
Correct |
1 ms |
1868 KB |
Output is correct |
9 |
Correct |
1 ms |
1868 KB |
Output is correct |
10 |
Correct |
1 ms |
1868 KB |
Output is correct |
11 |
Correct |
1 ms |
1868 KB |
Output is correct |
12 |
Correct |
1 ms |
1844 KB |
Output is correct |
13 |
Correct |
1 ms |
1868 KB |
Output is correct |
14 |
Correct |
1 ms |
1868 KB |
Output is correct |
15 |
Correct |
1 ms |
1868 KB |
Output is correct |
16 |
Correct |
1 ms |
1868 KB |
Output is correct |
17 |
Correct |
1 ms |
1868 KB |
Output is correct |
18 |
Correct |
56 ms |
8432 KB |
Output is correct |
19 |
Correct |
56 ms |
8368 KB |
Output is correct |
20 |
Correct |
57 ms |
8368 KB |
Output is correct |
21 |
Correct |
55 ms |
8432 KB |
Output is correct |
22 |
Correct |
58 ms |
8432 KB |
Output is correct |
23 |
Correct |
56 ms |
8432 KB |
Output is correct |
24 |
Correct |
55 ms |
8364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
51 ms |
8232 KB |
Output is correct |
3 |
Correct |
56 ms |
9440 KB |
Output is correct |
4 |
Correct |
56 ms |
9500 KB |
Output is correct |
5 |
Correct |
58 ms |
9372 KB |
Output is correct |
6 |
Correct |
2 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
1868 KB |
Output is correct |
8 |
Correct |
1 ms |
1868 KB |
Output is correct |
9 |
Correct |
1 ms |
1868 KB |
Output is correct |
10 |
Correct |
1 ms |
1868 KB |
Output is correct |
11 |
Correct |
1 ms |
1868 KB |
Output is correct |
12 |
Correct |
1 ms |
1860 KB |
Output is correct |
13 |
Correct |
1 ms |
1860 KB |
Output is correct |
14 |
Correct |
1 ms |
1820 KB |
Output is correct |
15 |
Correct |
1 ms |
1840 KB |
Output is correct |
16 |
Correct |
1 ms |
1872 KB |
Output is correct |
17 |
Correct |
1 ms |
1828 KB |
Output is correct |
18 |
Correct |
51 ms |
9508 KB |
Output is correct |
19 |
Correct |
51 ms |
9520 KB |
Output is correct |
20 |
Correct |
52 ms |
9504 KB |
Output is correct |
21 |
Correct |
55 ms |
9508 KB |
Output is correct |
22 |
Correct |
51 ms |
9500 KB |
Output is correct |
23 |
Correct |
44 ms |
9496 KB |
Output is correct |
24 |
Correct |
46 ms |
9464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
1868 KB |
Output is correct |
3 |
Correct |
1 ms |
1868 KB |
Output is correct |
4 |
Correct |
1 ms |
1868 KB |
Output is correct |
5 |
Correct |
1 ms |
1868 KB |
Output is correct |
6 |
Correct |
1 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
1836 KB |
Output is correct |
8 |
Correct |
1 ms |
1868 KB |
Output is correct |
9 |
Correct |
1 ms |
1836 KB |
Output is correct |
10 |
Correct |
1 ms |
1868 KB |
Output is correct |
11 |
Correct |
1 ms |
1872 KB |
Output is correct |
12 |
Correct |
1 ms |
1868 KB |
Output is correct |
13 |
Correct |
1 ms |
1872 KB |
Output is correct |
14 |
Correct |
1 ms |
1868 KB |
Output is correct |
15 |
Correct |
2 ms |
1880 KB |
Output is correct |
16 |
Correct |
1 ms |
1872 KB |
Output is correct |
17 |
Correct |
2 ms |
1868 KB |
Output is correct |
18 |
Correct |
1 ms |
1868 KB |
Output is correct |
19 |
Correct |
35 ms |
6704 KB |
Output is correct |
20 |
Correct |
33 ms |
7984 KB |
Output is correct |
21 |
Correct |
34 ms |
8012 KB |
Output is correct |
22 |
Correct |
45 ms |
9540 KB |
Output is correct |
23 |
Correct |
45 ms |
9520 KB |
Output is correct |
24 |
Correct |
44 ms |
9520 KB |
Output is correct |
25 |
Correct |
44 ms |
9536 KB |
Output is correct |
26 |
Correct |
1 ms |
1868 KB |
Output is correct |
27 |
Correct |
1 ms |
1868 KB |
Output is correct |
28 |
Correct |
57 ms |
8308 KB |
Output is correct |
29 |
Correct |
56 ms |
8368 KB |
Output is correct |
30 |
Correct |
1 ms |
1836 KB |
Output is correct |
31 |
Correct |
1 ms |
1868 KB |
Output is correct |
32 |
Correct |
1 ms |
1872 KB |
Output is correct |
33 |
Correct |
1 ms |
1868 KB |
Output is correct |
34 |
Correct |
1 ms |
1868 KB |
Output is correct |
35 |
Correct |
1 ms |
1868 KB |
Output is correct |
36 |
Correct |
1 ms |
1868 KB |
Output is correct |
37 |
Correct |
1 ms |
1844 KB |
Output is correct |
38 |
Correct |
1 ms |
1868 KB |
Output is correct |
39 |
Correct |
1 ms |
1868 KB |
Output is correct |
40 |
Correct |
1 ms |
1868 KB |
Output is correct |
41 |
Correct |
1 ms |
1868 KB |
Output is correct |
42 |
Correct |
1 ms |
1868 KB |
Output is correct |
43 |
Correct |
56 ms |
8432 KB |
Output is correct |
44 |
Correct |
56 ms |
8368 KB |
Output is correct |
45 |
Correct |
57 ms |
8368 KB |
Output is correct |
46 |
Correct |
55 ms |
8432 KB |
Output is correct |
47 |
Correct |
58 ms |
8432 KB |
Output is correct |
48 |
Correct |
56 ms |
8432 KB |
Output is correct |
49 |
Correct |
55 ms |
8364 KB |
Output is correct |
50 |
Correct |
1 ms |
1868 KB |
Output is correct |
51 |
Correct |
51 ms |
8232 KB |
Output is correct |
52 |
Correct |
56 ms |
9440 KB |
Output is correct |
53 |
Correct |
56 ms |
9500 KB |
Output is correct |
54 |
Correct |
58 ms |
9372 KB |
Output is correct |
55 |
Correct |
2 ms |
1868 KB |
Output is correct |
56 |
Correct |
1 ms |
1868 KB |
Output is correct |
57 |
Correct |
1 ms |
1868 KB |
Output is correct |
58 |
Correct |
1 ms |
1868 KB |
Output is correct |
59 |
Correct |
1 ms |
1868 KB |
Output is correct |
60 |
Correct |
1 ms |
1868 KB |
Output is correct |
61 |
Correct |
1 ms |
1860 KB |
Output is correct |
62 |
Correct |
1 ms |
1860 KB |
Output is correct |
63 |
Correct |
1 ms |
1820 KB |
Output is correct |
64 |
Correct |
1 ms |
1840 KB |
Output is correct |
65 |
Correct |
1 ms |
1872 KB |
Output is correct |
66 |
Correct |
1 ms |
1828 KB |
Output is correct |
67 |
Correct |
51 ms |
9508 KB |
Output is correct |
68 |
Correct |
51 ms |
9520 KB |
Output is correct |
69 |
Correct |
52 ms |
9504 KB |
Output is correct |
70 |
Correct |
55 ms |
9508 KB |
Output is correct |
71 |
Correct |
51 ms |
9500 KB |
Output is correct |
72 |
Correct |
44 ms |
9496 KB |
Output is correct |
73 |
Correct |
46 ms |
9464 KB |
Output is correct |
74 |
Correct |
46 ms |
10144 KB |
Output is correct |
75 |
Correct |
55 ms |
9776 KB |
Output is correct |
76 |
Correct |
56 ms |
10124 KB |
Output is correct |
77 |
Correct |
54 ms |
9648 KB |
Output is correct |
78 |
Correct |
49 ms |
9592 KB |
Output is correct |
79 |
Correct |
53 ms |
9520 KB |
Output is correct |
80 |
Correct |
46 ms |
9492 KB |
Output is correct |
81 |
Correct |
47 ms |
9656 KB |
Output is correct |
82 |
Correct |
43 ms |
9632 KB |
Output is correct |
83 |
Correct |
49 ms |
9760 KB |
Output is correct |
84 |
Correct |
69 ms |
10136 KB |
Output is correct |
85 |
Correct |
54 ms |
10176 KB |
Output is correct |
86 |
Correct |
48 ms |
10144 KB |
Output is correct |
87 |
Correct |
51 ms |
10140 KB |
Output is correct |
88 |
Correct |
52 ms |
10128 KB |
Output is correct |
89 |
Correct |
49 ms |
10140 KB |
Output is correct |
90 |
Correct |
59 ms |
10148 KB |
Output is correct |
91 |
Correct |
48 ms |
10144 KB |
Output is correct |
92 |
Correct |
60 ms |
10140 KB |
Output is correct |
93 |
Correct |
48 ms |
10160 KB |
Output is correct |
94 |
Correct |
52 ms |
10148 KB |
Output is correct |
95 |
Correct |
55 ms |
10160 KB |
Output is correct |
96 |
Correct |
48 ms |
10160 KB |
Output is correct |
97 |
Correct |
47 ms |
10128 KB |
Output is correct |
98 |
Correct |
52 ms |
10140 KB |
Output is correct |
99 |
Correct |
51 ms |
10160 KB |
Output is correct |
100 |
Correct |
56 ms |
10148 KB |
Output is correct |
101 |
Correct |
48 ms |
10152 KB |
Output is correct |
102 |
Correct |
58 ms |
10168 KB |
Output is correct |