Submission #262252

#	Time	Username	Problem	Language	Result	Execution time	Memory
262252		youssefbou62	Wiring (IOI17_wiring)	C++14	0 / 100	23 ms	19448 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++ ){
		for(int j = 0 ; j < sz(adj[i]) ; j++ ){

			for(int k = 0 ; k <= j ; k++ ){
				if( i == R-1){
					continue ; 
				}
				int in = find(all(adj[i+1]),adj[i][k])-adj[i].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 ; 
				int in = find(all(adj[x]),adj[i][j])-adj[x].begin() ;

				mins(dp[i][j+1],dp[i][j]+1LL*abs(r[x]-b[adj[i][j]]));  
					
			}
			// if( j <	 sz(adj[i])  ){
			mins(dp[i+1][j+1],dp[i][j]+1LL*abs(r[i]-b[adj[i][j]])); 
			// }
			// cout << i << " " << j << " " << dp[i][j]<<endl; 
		}
	}
	// return 0 ;
	return dp[R][sz(adj[R-1])] ; 
}



// 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:67:9: warning: unused variable 'in' [-Wunused-variable]
   67 |     int in = find(all(adj[x]),adj[i][j])-adj[x].begin() ;
      |         ^~
wiring.cpp:21:5: warning: unused variable 'ans' [-Wunused-variable]
   21 |  ll ans = 1e18 ;
      |     ^~~

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