Submission #419941

#	Time	Username	Problem	Language	Result	Execution time	Memory
419941		Blagojce	Wiring (IOI17_wiring)	C++11	100 / 100	86 ms	13596 KiB

wiring

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5e5+5;

#include "wiring.h"


long long min_total_length(std::vector<int> r, std::vector<int> b){
	vector<pair<int, int> > v;
	for(auto u : r) v.pb({u, 0});
	for(auto u : b) v.pb({u, 1});
	sort(all(v));
	
	int n = (int)v.size();
	
	vector<vector<ll> > g;
		
	int col = -1;
	fr(i, 0, n){
		if(v[i].nd != col) g.pb({});
		g.back().pb(v[i].st);
		col = v[i].nd;
	}
	int m = g.size();
	
	vector<ll> dp[m];
	
	ll s = 0;
	
	fr(i, 0, (int)g[0].size()){
		s += g[1][0] - g[0][i];
		dp[0].pb(s);
	}
	reverse(all(dp[0]));
	dp[0].pb(0);
	fr(i, 1, m){
		int s1 = g[i].size();
		ll pref[s1+1];
		pref[0] = 0;
		s = 0;
		fr(j, 0, s1){
			s += g[i][j];
			pref[j+1] = s;
		}
		
		
		int s2 = g[i-1].size();
		ll suff[s2+1];
		suff[0] = 0;
		s = 0;
		fr(j, 0, s2){
			s += g[i-1][s2 - j - 1];
			suff[j+1] = s;
		}
		
		dp[i].resize(s1+1);
		fr(j, 0, s1+1) dp[i][j] = inf;
		
		fr(j, 0, min(s1, s2) + 1){
			ll cost = pref[j] - suff[j];
			dp[i][s1-j] = dp[i-1][j] + cost;
		}
		if(i + 1 < m){

			for(int j = s1; j >= 1; j --){
				dp[i][j-1] = min(dp[i][j-1], dp[i][j] + min(g[i+1][0] - g[i][s1 - j], g[i][s1-j] - g[i-1].back()));
			}
		}
	}
	int lsz = (int)g.back().size();
	
	ll ans = dp[m-1][0];
	
	ll add = 0;
	fr(i, 0, lsz){
		add += g[m-1][lsz-i-1] - g[m-2].back();
		ans = min(ans, dp[m-1][i+1] + add);
	}
	
	
	
	
	return ans;
	
}

/*
int main(){
	cout<<min_total_length({1, 2, 3}, {6, 10});
}
*/

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45