Submission #262291

#	Time	Username	Problem	Language	Result	Execution time	Memory
262291		youssefbou62	Wiring (IOI17_wiring)	C++14	0 / 100	65 ms	29112 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 ;

ll dp[MAXN][20];  
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 ;  
	for(int i = 0 ; i <= R ; i++ )for(int j = 0 ; j <= 19 ; j++ )dp[i][j] = 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 ; 
	// }

	for(int i = 0 ; i < R ; i++ ){
		// cout << i << " " 
		for(int j = 0 ; j < sz(adj[i]) ; j++ ){

			for(int k = 0 ; k < j ; k++ ){
				int in = find(all(adj[i+1]),adj[i][k])-adj[i+1].begin() ; 
				if( in == sz(adj[i+1]))in = 0;
				mins(dp[i+1][in],dp[i][j]+1LL*abs(r[i]-b[adj[i][k]]));  
			}
			for(int x : adj1[adj[i][j]]){
					if( x > i)break ; 
					if( j == sz(adj[i])-1 )
						mins(ans,dp[R][0]+1LL*abs(r[x]-b[adj[i][j]])); 
					mins(dp[i][j+1],dp[i][j]+1LL*abs(r[x]-b[adj[i][j]])); 	
				
			}
			
			int in = find(all(adj[i+1]),adj[i][j])-adj[i+1].begin() ;
			if( i == R-1 && j == sz(adj[i])-1)
				mins(ans,dp[i][j]+1LL*abs(r[i]-b[adj[i][j]])); 
			if( in == sz(adj[i+1]))in=-1;
			mins(dp[i+1][in+1],dp[i][j]+1LL*abs(r[i]-b[adj[i][j]])); 
		
		}
	}

	return ans ; 
}



// 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