제출 #262398

#제출 시각아이디문제언어결과실행 시간메모리
262398youssefbou62전선 연결 (IOI17_wiring)C++14
0 / 100
134 ms33512 KiB
#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]; int R,B; void mins(ll& a ,ll b ){ a = min ( a , b ) ; } vector<int> rr , bb ; ll solve (int i ,int u ){ // if( j >= sz(adj[i]) )return 1e18 ; // int u = adj[i][j] ; if( lower_bound(all(adj[i]),u) == adj[i].end() ) return 1e18 ; if( i == R && u == B ){ return 0 ; } // cout << i << " " << j << endl; if( dp[i].count(u) ) return dp[i][u] ; ll& r = dp[i][u] ; r = 1e18 ; if( i < R && u < B){ int x = *upper_bound(all(adj[i+1]),u); if( x != B || u == B-1 ) r = min(r,solve(i+1,x)+1LL*abs( rr[i] - bb[u] ) ); } // cout << i << " *******" << u << endl; if( u < B ){ int y = *upper_bound(all(adj[i]),u); for(int x : adj1[u]){ if( x >= i )continue ; // if( i == 4 )cout << "x,u"<<x<<" " <<u <<" " << y << endl; if( y == B && u != B-1 )continue ; r = min(r,solve(i,y)+1LL*abs(rr[x]-bb[u])); } } // cout << i << " *******" << u << endl; if( i < R ) for(int k = 0 ; k < sz(adj[i]) ; k++ ){ int v = adj[i][k] ; if( v >= u )break ; r = min(r,solve(i+1,u)+1LL*abs(rr[i]-bb[v])); } // 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<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); } } }for(int i=0 ; i< R; i++ ){ sort(all(adj[i])); adj[i].pb(B); } adj[R] = adj[R-1]; return solve(0,adj[0][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; // } //
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...