Submission #262346

#	Time	Username	Problem	Language	Result	Execution time	Memory
262346		youssefbou62	Wiring (IOI17_wiring)	C++14	0 / 100	42 ms	38528 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define sz(x)	(int)x.size()
#define ll long long  
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first 
#define se second 
using namespace std; 

const int MAXN = 2e5+1 ;
map<int,ll> dp[MAXN];  
vector<int> adj[MAXN],adj1[MAXN]; 

void mins(ll& a ,ll b ){
	a = min ( a , b ) ; 
}



long long min_total_length(vector<int> r, vector<int> b) {
	int R = sz(r) , B = sz(b) ;
	vector<pair<int,int>> connections; 
	for(int i = 0 ; i < R ; i++ ){
		connections.pb({r[i],-i-1}); 
	}
	for(int i = 0 ; i < B ; i++ ){
		connections.pb({b[i],i+1}); 
	}
	sort(all(connections));  
	for(int i = 0 ; i < sz(connections); i++ ){
		if(connections[i].se < 0 ){ 
			for(int j = i - 6 ; j <= i + 6 && j<sz(connections) ; j++ ){
				if( j < 0  )continue  ; 
				if( connections[j].se < 0 )continue ; 
				adj[-connections[i].se-1].pb(connections[j].se-1); 
		}
		}else{
			for(int j = i - 6 ; j <= i + 6 && j<sz(connections) ; j++ ){
				if( j < 0  )continue  ; 
				if( connections[j].se > 0 )continue ; 
				adj1[connections[i].se-1].pb(-connections[j].se-1); 
			}
		}
	}

	dp[0][0] = 0 ; 
	// for(int i = 0 ; i<B ; i++ ){
	// 	cerr << i << endl; 
	// 	for(int j : adj1[i]){
	// 		cout << j << " " ; 
	// 	}cout << endl ; 
	// }
	adj[R] = adj[R-1]; 
	for(int i = 0 ; i <= R ; i++ ){
		// cout << i << " "

		adj[i].pb(B);  
		for(int j = 0 ; j <= sz(adj[i]) ; j++ ){ 
			if( i == R && j == sz(adj[i]))continue ; 
			int u = adj[i][j] ; 	
			if( !dp[i].count(u))continue ;
			for(int k = 0 ; k < j ; k++ ){
				int v = adj[i][k] ; 
				if( !dp[i+1].count(u))
					dp[i+1][u] = 1e18 ; 
				mins(dp[i+1][u],dp[i][u]+1LL*abs(r[i]-b[v])); 
			}

			auto it  =find(all(adj[i+1]),u); 
			int x  ; 
			if( it != adj[i+1].end() && next(it)!=adj[i+1].end())
				x = *next(it) ; 
			else if( i != R )  x = adj[i+1][0] ; 
			if( i != R &&!dp[i+1].count(x))
					dp[i+1][x] = 1e18 ; 
			if( i != R )
			mins(dp[i+1][x],dp[i][u]+1LL*abs(r[i]-b[u])); 
			
			for(int k : adj1[u] ){
				if( k >= u )continue ; 
				if( j != sz(adj[i]) && !dp[i].count(adj[i][j+1]))
					dp[i][adj[i][j+1]] = 1e18 ; 
				else mins(dp[i][adj[i][j+1]],dp[i][u]+1LL*abs(r[k]-b[u])); 
			} 
			// cout << i << " " << u << " " << dp[i][u] << endl; 
		}
	}

	return dp[R][B] ; 
}



// int main() {
// 	int n, m;
// 	assert(2 == scanf("%d %d", &n, &m));

// 	vector<int> 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;
// }

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