Submission #262316

#	Time	Username	Problem	Language	Result	Execution time	Memory
262316		youssefbou62	Wiring (IOI17_wiring)	C++14	0 / 100	149 ms	32800 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) ;
	ll ans = 1e18 ;  
	

	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++ ){ 
			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] = dp[i][u]+1LL*abs(r[i]-b[v]); 
				else 
				mins(dp[i+1][u],dp[i][u]+1LL*abs(r[i]-b[v])); 
			}
			if( !dp[i+1].count(u+1))dp[i+1][u+1]=dp[i][u]+1LL*abs(r[i]-b[u]); 
			else 
			mins(dp[i+1][u+1],dp[i][u]+1LL*abs(r[i]-b[u])); 
			for(int k : adj1[u] ){
				if( k > u )break ; 
				if( !dp[i].count(u+1))dp[i][u+1] = dp[i][u]+1LL*abs(r[k]-b[u]); 
				else mins(dp[i][u+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;
}
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:23:5: warning: unused variable 'ans' [-Wunused-variable]
   23 |  ll ans = 1e18 ;
      |     ^~~

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