#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> seqinds;
vector<ll> prefl;
vector<ll> prefr;
vector<ll> dl;
vector<ll> dr;
vector<ll> len;
ll n;
ll ns;
ll INF = 1e18;
void processData(vector<int> &r, vector<int> &b){
vector<pair<ll,bool>> seq;
for (ll i : r){
seq.push_back({i,false});
}
for (ll i : b){
seq.push_back({i,true});
}
n = seq.size();
sort(seq.begin(),seq.end());
ll mx = seq.back().first;
for (auto p : seq){
dl.push_back(p.first);
dr.push_back(mx-p.first);
}
prefl.resize(n+1);
prefr.resize(n+1);
for (ll i = 0; i<n; i++){
prefl[i+1]=prefl[i]+dl[i];
}
for (ll i = n-1; i>=0; i--){
prefr[i]=prefr[i+1]+dr[i];
}
bool curval = seq[0].second;
ll curind = 0;
seqinds.push_back(curind);
for (ll i = 0; i<n; i++){
if (seq[i].second!=curval){
curind=i;
seqinds.push_back(curind);
curval=seq[i].second;
}
}
ns = seqinds.size();
seqinds.push_back(n);
for (ll i = 0; i<seqinds.size()-1; i++){
len.push_back(seqinds[i+1]-seqinds[i]);
}
}
void display(string s, vector<ll> &v){
cout<<s<<": ";
for (ll i : v){
cout<<i<<' ';
}cout<<'\n';
}
ll lsum(ll i, ll l){
ll xi = seqinds[i];
return prefl[xi+l]-prefl[xi]-l*dl[xi];
}
ll rsum(ll i, ll r){
ll xi1 = seqinds[i+1];
return prefr[xi1-r]-prefr[xi1]-r*dr[xi1];
}
ll performDP(){
ll mxlen = 0;
for (ll i : len){
mxlen=max(mxlen,i);
}
vector<vector<ll>> dp(2,vector<ll>(mxlen+1,INF));
vector<vector<ll>> dpgeq(2,vector<ll>(mxlen+1,INF));
bool cur = false;
dp[!cur][0]=0;
dpgeq[!cur][0]=0;
for (ll i = 0; i<ns; i++){
//cout<<"dp "<<i<<endl;
ll xi1 = seqinds[i+1];
ll ci = dr[xi1-1]-dr[xi1];
ll minpref = INF;
ll maxprev = max(len[i],((i==0)?0:len[i-1]));
//ll maxprev = mxlen;
for (ll r = 0; r<=maxprev; r++){
ll newl = len[i]-r;
if (newl<0){newl=0;}
ll newmin = dp[!cur][newl]+lsum(i,newl)+rsum(i,len[i]-newl)+ci*newl;
//cout<<"at r = "<<r<<": new value is "<<newmin<<'\n';
minpref=min(minpref,newmin);
dp[cur][r]=minpref+ci*(r-len[i]);
}
if (i==ns-1){break;}
for (ll r = maxprev+1; r<=len[i+1]; r++){
dp[cur][r]=dp[cur][r-1]+ci;
}
/*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
cout<<dp[cur][x]<<' ';
}cout<<'\n';*/
for (ll r = max(maxprev,len[i+1])-1; r>=0; r--){
dp[cur][r]=min(dp[cur][r],dp[cur][r+1]);
}
/*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
cout<<dp[cur][x]<<' ';
}cout<<'\n';*/
cur=!cur;
}
/*for (int i = 0; i<ns; i++){
for (int r = 0; r<mxlen; r++){
//dp(i,r)
for (int l = max(len[i]-r,0); l<=len[i]; l++){
dp[cur][r]=min(dp[cur][r])
}
}
}*/
return dp[cur][0];
}
ll min_total_length(std::vector<int> r, std::vector<int> b) {
processData(r,b);
/*display("seqinds",seqinds);
display("prefl",prefl);
display("prefr",prefr);
display("len",len);
display("distance l",dl);
display("distance r",dr);*/
/*while (true){
char c;
ll a,b;
cin>>c>>a>>b;
if (c=='l'){
cout<<lsum(a,b)<<endl;
} else if (c=='r'){
cout<<rsum(a,b)<<endl;
} else {
assert(1==0);
}
}*/
return performDP();
}
Compilation message
wiring.cpp: In function 'void processData(std::vector<int>&, std::vector<int>&)':
wiring.cpp:56:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (ll i = 0; i<seqinds.size()-1; i++){
| ~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
288 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
44 ms |
12604 KB |
Output is correct |
4 |
Correct |
43 ms |
12776 KB |
Output is correct |
5 |
Correct |
42 ms |
12692 KB |
Output is correct |
6 |
Correct |
55 ms |
15076 KB |
Output is correct |
7 |
Correct |
53 ms |
15076 KB |
Output is correct |
8 |
Correct |
55 ms |
15076 KB |
Output is correct |
9 |
Correct |
55 ms |
15152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
68 ms |
15460 KB |
Output is correct |
4 |
Correct |
64 ms |
14948 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
68 ms |
15456 KB |
Output is correct |
19 |
Correct |
66 ms |
15612 KB |
Output is correct |
20 |
Correct |
69 ms |
15328 KB |
Output is correct |
21 |
Correct |
68 ms |
15456 KB |
Output is correct |
22 |
Correct |
68 ms |
15456 KB |
Output is correct |
23 |
Correct |
70 ms |
15456 KB |
Output is correct |
24 |
Correct |
68 ms |
15460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
55 ms |
14348 KB |
Output is correct |
3 |
Correct |
58 ms |
14436 KB |
Output is correct |
4 |
Correct |
59 ms |
14436 KB |
Output is correct |
5 |
Correct |
58 ms |
14436 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
56 ms |
14412 KB |
Output is correct |
19 |
Correct |
57 ms |
14436 KB |
Output is correct |
20 |
Correct |
60 ms |
14424 KB |
Output is correct |
21 |
Correct |
51 ms |
14432 KB |
Output is correct |
22 |
Correct |
55 ms |
14436 KB |
Output is correct |
23 |
Correct |
51 ms |
14436 KB |
Output is correct |
24 |
Correct |
50 ms |
14436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
288 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
44 ms |
12604 KB |
Output is correct |
20 |
Correct |
43 ms |
12776 KB |
Output is correct |
21 |
Correct |
42 ms |
12692 KB |
Output is correct |
22 |
Correct |
55 ms |
15076 KB |
Output is correct |
23 |
Correct |
53 ms |
15076 KB |
Output is correct |
24 |
Correct |
55 ms |
15076 KB |
Output is correct |
25 |
Correct |
55 ms |
15152 KB |
Output is correct |
26 |
Correct |
0 ms |
256 KB |
Output is correct |
27 |
Correct |
0 ms |
256 KB |
Output is correct |
28 |
Correct |
68 ms |
15460 KB |
Output is correct |
29 |
Correct |
64 ms |
14948 KB |
Output is correct |
30 |
Correct |
0 ms |
256 KB |
Output is correct |
31 |
Correct |
0 ms |
256 KB |
Output is correct |
32 |
Correct |
0 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
256 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
256 KB |
Output is correct |
38 |
Correct |
0 ms |
256 KB |
Output is correct |
39 |
Correct |
0 ms |
256 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
256 KB |
Output is correct |
42 |
Correct |
0 ms |
384 KB |
Output is correct |
43 |
Correct |
68 ms |
15456 KB |
Output is correct |
44 |
Correct |
66 ms |
15612 KB |
Output is correct |
45 |
Correct |
69 ms |
15328 KB |
Output is correct |
46 |
Correct |
68 ms |
15456 KB |
Output is correct |
47 |
Correct |
68 ms |
15456 KB |
Output is correct |
48 |
Correct |
70 ms |
15456 KB |
Output is correct |
49 |
Correct |
68 ms |
15460 KB |
Output is correct |
50 |
Correct |
0 ms |
256 KB |
Output is correct |
51 |
Correct |
55 ms |
14348 KB |
Output is correct |
52 |
Correct |
58 ms |
14436 KB |
Output is correct |
53 |
Correct |
59 ms |
14436 KB |
Output is correct |
54 |
Correct |
58 ms |
14436 KB |
Output is correct |
55 |
Correct |
0 ms |
384 KB |
Output is correct |
56 |
Correct |
0 ms |
256 KB |
Output is correct |
57 |
Correct |
1 ms |
256 KB |
Output is correct |
58 |
Correct |
1 ms |
256 KB |
Output is correct |
59 |
Correct |
0 ms |
256 KB |
Output is correct |
60 |
Correct |
1 ms |
256 KB |
Output is correct |
61 |
Correct |
0 ms |
256 KB |
Output is correct |
62 |
Correct |
0 ms |
256 KB |
Output is correct |
63 |
Correct |
0 ms |
256 KB |
Output is correct |
64 |
Correct |
1 ms |
384 KB |
Output is correct |
65 |
Correct |
0 ms |
256 KB |
Output is correct |
66 |
Correct |
0 ms |
384 KB |
Output is correct |
67 |
Correct |
56 ms |
14412 KB |
Output is correct |
68 |
Correct |
57 ms |
14436 KB |
Output is correct |
69 |
Correct |
60 ms |
14424 KB |
Output is correct |
70 |
Correct |
51 ms |
14432 KB |
Output is correct |
71 |
Correct |
55 ms |
14436 KB |
Output is correct |
72 |
Correct |
51 ms |
14436 KB |
Output is correct |
73 |
Correct |
50 ms |
14436 KB |
Output is correct |
74 |
Correct |
55 ms |
15076 KB |
Output is correct |
75 |
Correct |
62 ms |
14692 KB |
Output is correct |
76 |
Correct |
64 ms |
15076 KB |
Output is correct |
77 |
Correct |
57 ms |
14560 KB |
Output is correct |
78 |
Correct |
56 ms |
14436 KB |
Output is correct |
79 |
Correct |
57 ms |
14432 KB |
Output is correct |
80 |
Correct |
50 ms |
14436 KB |
Output is correct |
81 |
Correct |
57 ms |
14564 KB |
Output is correct |
82 |
Correct |
55 ms |
14568 KB |
Output is correct |
83 |
Correct |
51 ms |
14752 KB |
Output is correct |
84 |
Correct |
57 ms |
15076 KB |
Output is correct |
85 |
Correct |
63 ms |
15080 KB |
Output is correct |
86 |
Correct |
56 ms |
15076 KB |
Output is correct |
87 |
Correct |
59 ms |
15072 KB |
Output is correct |
88 |
Correct |
60 ms |
15076 KB |
Output is correct |
89 |
Correct |
58 ms |
15076 KB |
Output is correct |
90 |
Correct |
65 ms |
15076 KB |
Output is correct |
91 |
Correct |
57 ms |
15076 KB |
Output is correct |
92 |
Correct |
69 ms |
15080 KB |
Output is correct |
93 |
Correct |
57 ms |
15076 KB |
Output is correct |
94 |
Correct |
62 ms |
15084 KB |
Output is correct |
95 |
Correct |
61 ms |
15076 KB |
Output is correct |
96 |
Correct |
56 ms |
15080 KB |
Output is correct |
97 |
Correct |
57 ms |
15076 KB |
Output is correct |
98 |
Correct |
59 ms |
15076 KB |
Output is correct |
99 |
Correct |
58 ms |
15076 KB |
Output is correct |
100 |
Correct |
63 ms |
15072 KB |
Output is correct |
101 |
Correct |
59 ms |
15076 KB |
Output is correct |
102 |
Correct |
65 ms |
15072 KB |
Output is correct |