Submission #262432

#	Time	Username	Problem	Language	Result	Execution time	Memory
262432		youssefbou62	전선 연결 (IOI17_wiring)	C++14	0 / 100	205 ms	94108 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];
int R,B; 
int Le[MAXN],Ri[MAXN]; 
int Le1[MAXN],Ri1[MAXN];

void mins(ll& a ,ll b ){
	a = min ( a , b ) ; 
}
vector<int> rr , bb ; 
 
ll solve (int i ,int u ){

	if( i == R && u == B ){
		return 0 ; 
	}
	if( u > Ri[i] )
		u = Ri[i] ; 
	if( u < Le[i])
		u = Le[i] ; 
	int j = u - Le[i] ;

	ll& r = dp[i][j];

	if( r != -1 )
		return r;
	r = 1e18 ; 
	if( i < R && u < B ){
		r = min(r,solve(i+1,u+1)+1LL*abs(rr[i]-bb[u])); 
		// cout << i << " " << u << "* " << abs(rr[i]-bb[u])<<endl;
		// cout << i + 1 << " i+1 " << u + 1 << " u + 1 "<<solve(i+1,u+1)<<endl;  
	}
	if( i < R ){
		ll s = solve(i+1,u); 
		for(int k = Le[i] ; k <= u ; k++ ){
			r=min(r,s+1LL*abs(rr[i]-bb[k])); 
		}
	}

	if( u < B ){
		ll s = solve(i,u+1); 
		for(int k = Le1[u] ; k <= i && k <= Ri1[u] ; k++ ){
			r=min(r,s+1LL*abs(rr[k]-bb[u]));
			// cout << solve(i,u+1) << " " << abs(rr[k]-bb[u]) <<endl; 

		}

	}
	// cout << i << " " << u << " " << r << endl;  
	
	return r;  
}

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

			int x = connections[i][1] , y  =connections[j][1] ;    
			if(connections[i][2]==0&&connections[j][2]){
				Ri[x]=max(Ri[x],y); 
				Le[x]=min(Le[x],y); 
			}
			 if(connections[i][2]&&connections[j][2]==0){
				Ri1[x]=max(Ri1[x],y); 
				Le1[x]=min(Le1[x],y); 
			}
		}
	}

	memset(dp,-1,sizeof dp); 
	Ri[R]=Ri[R-1];  
	Le[R]=Le[R-1];
	Ri1[B]=Ri1[B-1]; 
	Le1[B]=Le1[B-1]; 
	

	for(int i =0;i<=R;i++)
		assert(Ri[i]-Le[i]<=15); 
	for(int i =0;i<=B;i++)
		assert(Ri1[i]-Le1[i]<=15); 	
	return solve(0,Le[0]) ; 
}



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