Submission #262254

#TimeUsernameProblemLanguageResultExecution timeMemory
262254youssefbou62Wiring (IOI17_wiring)C++14
0 / 100
20 ms19456 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]; 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]) ){ int in = find(all(adj[i]),adj[i][j])-adj[i].begin() ; if( in == sz(adj[i]) )in = -1; mins(dp[i+1][in+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 ;
      |     ^~~
#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...