This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
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;
for (int i=a.size()-2;i>-1;i--){
ll id=i;
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;
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]));
}
// 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 (stderr)
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:44: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]
44 | for (int i=1;i<a.size();i++){
| ~^~~~~~~~~
wiring.cpp:51: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]
51 | while(id<a.size() && a[id].S==a[i].S) id++;
| ~~^~~~~~~~~
wiring.cpp:52: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]
52 | if (id==a.size()) continue;
| ~~^~~~~~~~~~
wiring.cpp:54: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]
54 | while(id2<a.size() && a[id2].S==a[id].S) id2++;
| ~~~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |