Submission #424440

#TimeUsernameProblemLanguageResultExecution timeMemory
424440arnevesWiring (IOI17_wiring)C++17
42 / 100
74 ms15032 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=200'005; /* 4 5 1 2 3 7 0 4 5 9 10 */ long long min_total_length(std::vector<int> r, std::vector<int> b) { int n=r.size(); int m=b.size(); vector<pair<ll,bool>> a; a.push_back({-1,0}); for(int i=0; i<n; i++){ a.push_back({r[i],0}); } for(int i=0; i<m; i++){ a.push_back({b[i],1}); } sort(a.begin(),a.end()); ll dp[MX]; dp[0]=0; ll soma_b[MX], soma_r[MX]; for(int i=1; i<=n+m; i++){ soma_b[i]=soma_b[i-1]; soma_r[i]=soma_r[i-1]; if(a[i].second){ soma_b[i]+=a[i].first; }else{ soma_r[i]+=a[i].first; } } int temp[2*MX]; int indice_anterior[MX]; memset(temp,-1, sizeof(temp)); memset(indice_anterior,-1,sizeof(indice_anterior)); int j=n+m; temp[n+m]=0; for(int i=1; i<=n+m; i++){ if(a[i].second){ j++; }else{ j--; } if(temp[j]!=-1){ indice_anterior[i]=temp[j]; } temp[j]=i; } for(int i=1; i<=n+m; i++){ //cout<<"->"<<i<<' '<<dp[i-1]<<'\n'; ll ans=MX; if(a[i].second){ auto u=lower_bound(r.begin(),r.end(),a[i].first); if(u!=r.end()) ans=min(ans,*u-a[i].first); if(u!=r.begin()){ u--; ans=min(ans,a[i].first-*u); } }else{ auto u=lower_bound(b.begin(),b.end(),a[i].first); if(u!=b.end()) ans=min(ans,*u-a[i].first); if(u!=b.begin()){ u--; ans=min(ans,a[i].first-*u); } } dp[i]=dp[i-1]+ans; if(indice_anterior[i]!=-1){ dp[i]=min(dp[i],dp[indice_anterior[i]]+abs((soma_r[i]-soma_r[indice_anterior[i]])-(soma_b[i]-soma_b[indice_anterior[i]]))); } } return dp[n+m]; }
#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...