#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "wiring.h"
ll min_total_length(vector<int> r_g, vector<int> b_g) {
vi r, b;
for (int x : r_g)
r.pb(x);
for (int x : b_g)
b.pb(x);
int N = r.size();
int M = b.size();
vector<ii> vals;
for (int i = 0; i < N; i++) {
vals.pb({r[i], 0});
}
for (int i = 0; i < M; i++) {
vals.pb({b[i], 1});
}
vals.pb({-1e18, -1});
sort(vals.begin(), vals.end());
/* cout<<"vals: ";
for (ii p : vals)
cout<<"("<<p.fi<<", "<<p.se<<"); ";
cout<<endl;*/
int K = N + M;
vals[0].se - 1 - vals[1].se; // opposite start as placeholder
vi pfs(K + 1, 0);
for (int i = 1; i <= K; i++) {
pfs[i] = pfs[i - 1] + vals[i].fi;
}
/* cout<<"pfs: ";
for (ll x : pfs)
cout<<x<<" ";
cout<<endl;*/
vi dp(K + 1, 0);
ll prev = 1;
for (ll i = 1; i <= K; i++) { // i = start of comp
ll j = i; // j = end of comp
while (j < K && vals[j].se == vals[j + 1].se)
j++;
ll minv = dp[i - 1];
ll sum = 0; // total connection cost to i - 1
for (int k = i; k <= j; k++) {
sum += (vals[k].fi - vals[i - 1].fi);
ll vc = 2 * i - k - 1; // paired (vc, k), (vc + 1, k - 1), up to (i - 1, i)
if (vc >= prev) {
ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1])
// toadd: extra connection cost from pairing w/ vc, vc+1, ... instead of all w/ i-1
minv = min(minv, dp[vc - 1] + toadd);
}
dp[k] = minv + sum;
}
prev = i;
i = j;
}
return dp[K];
}
Compilation message
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:17: warning: value computed is not used [-Wunused-value]
37 | vals[0].se - 1 - vals[1].se; // opposite start as placeholder
wiring.cpp:61:5: error: expected ',' or ';' before 'minv'
61 | minv = min(minv, dp[vc - 1] + toadd);
| ^~~~
wiring.cpp:59:8: warning: unused variable 'toadd' [-Wunused-variable]
59 | ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1])
| ^~~~~
