제출 #262422

#제출 시각아이디문제언어결과실행 시간메모리
262422youssefbou62전선 연결 (IOI17_wiring)C++14
0 / 100
71 ms31820 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 ; 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 ; } int j = u - Le[i] ; if( j > 7 )return solve(i+1,u); ll& r = dp[i][j]; if( r != -1 ) return r; r = 1e18 ; if( i < R && u < B ){ r = min(r,solve(i+1,max(Le[i+1],u+1))+1LL*abs(rr[i]-bb[u])); } if( i < R ){ for(int k = Le[i] ; k <= u ; k++ ) r=min(r,solve(i+1,u)+1LL*abs(rr[i]-bb[k])); } int x = 1e9 ; if( u < B ){ for(int k = Le1[u] ; k <= i && k <= Ri1[u] ; k++ ){ r=min(r,solve(i,u+1)+1LL*abs(rr[k]-bb[u])); x = min(x,abs(rr[k]-bb[u])); } } // cout << i << " " << u << " " << x << 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]){ Ri[x]=max(Ri[x],y); Le[x]=min(Le[x],y); }else{ Ri1[x]=max(Ri1[x],y); Le1[x]=min(Le1[x],y); } } } memset(dp,-1,sizeof dp); 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; // } //
#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...