# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924680 | 2024-02-09T12:43:59 Z | Dzadzo | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "wiring.h" #define ll long long #define int ll #define pb push_back #define S second #define F first #define pii pair<int,int> #define vi vector <int> #define vvi vector <vi> #define vvvi vector <vvi> #define vp vector <pii> #define vvp vector <vp> #define vb vector <bool> #define vvb vector <vb>; #define INF LLONG_MAX #define MOD 1000000007 #define MAXN 100000 using namespace std; ll min_total_length(vector<int> R, vector<int> B) { vp v; v.pb({0,0}); for (int x:R)v.pb({x,-1}); for (int x:B)v.pb({x,1}); int n=v.size()-1; sort(v.begin()+1,v.end()); vi dp(n+1,INF),p(n+1); dp[0]=0; for (int i=1;i<=n;i++){ p[i]=p[i-1]+v[i].F; } int cur=1,prev=0; while (v[prev].S==v[prev+1].S)cur++; int ind; for (int i=cur+1;i<=n;i++){ if (v[i].S!=v[i-1].S){ ind=v[i-1].F; for (int j=i-cur;j<i;j++)if (dp[j-1]!=INF)dp[j]=min(dp[j],dp[j-1]+v[i].F-v[j].F); prev=cur; cur=0; } cur++; if (dp[i-1]!=INF) dp[i]=min(dp[i],dp[i-1]+v[i].F-ind); if (cur<=prev && dp[i-2*cur]!=INF)dp[i]=min(dp[i],dp[i-2*cur]+p[i]+p[i-2*cur]-2*p[i-cur]); } return dp[n]; }