제출 #419933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419933		Blagojce	전선 연결 (IOI17_wiring)	C++11	0 / 100	1 ms	204 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<int> > g;
		
	int col = -1;
	fr(i, 0, n){
		if(v[i].nd != col) g.pb({});
		g.back().pb(i);
		col = v[i].nd;
	}
	int m = g.size();
	
	vector<ll> dp[m];
	
	int cnt[n];
	
	cnt[0] = 0;
	fr(i, 1, n){
		cnt[i] = 1;
		if(v[i].nd == v[i-1].nd) cnt[i] = cnt[i-1] + 1;
	}
	ll s = 0;
	dp[0].pb(0);
	fr(i, 0, (int)g[0].size()){
		s += v[g[1][0]].st - v[g[0][i]].st;
		dp[0].pb(s);
	}
	
	
	
	
	
	fr(i, 1, m){
		int s1 = g[i].size();
		ll pref[s1];
		pref[0] = 0;
		s = 0;
		fr(j, 0, s1){
			s += v[g[i][j]].st;
			pref[j+1] = s;
		}
		
		
		int s2 = g[i-1].size();
		ll suff[s2];
		suff[0] = 0;
		s = 0;
		fr(j, 0, s2){
			s += v[g[i-1][s2 - j - 1]].st;
			suff[j+1] = s;
		}
		
		dp[i].resize(s1+1);
		fr(j, 0, s1+1) dp[i][j] = 1e9;
		
		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] + v[g[i+1][0]].st - v[g[i][j-1]].st);
			}
		}
	}
	int lsz = (int)g.back().size();
	
	ll ans = dp[m-1][0];
	
	ll add = 0;
	fr(i, 0, lsz){
		add += v[g[m-1][lsz-i-1]].st - v[g[m-2].back()].st;
		ans = min(ans, dp[m-1][i+1] + add);
		
	}
	
	
	return ans;
	
}

 /*
int main(){
	cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10});
}

*/

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