Submission #363501

#TimeUsernameProblemLanguageResultExecution timeMemory
363501FystyWiring (IOI17_wiring)C++17
0 / 100
1 ms364 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; #define MottoHayaku ios::sync_with_stdio(0);cin.tie(0); #define rep1(i,n) for(int i=1;i<=n;i++) #define rep(i,n) for(int i=0;i<n;i++) #define F first #define S second #define pb push_back //#define int ll const int MOD=1e9+7; const ll INF=1e18; const int N=200005; ll dp[N],cnt[N]; ll min_total_length(vector<int> r,vector<int> b) { vector<pll> v; ll lastr=-INF,lastb=-INF,posr=-1,posb=-1; v.pb({-INF,-1}); for(int i=0;i<r.size();i++) v.pb({r[i],0}); for(int i=0;i<b.size();i++) v.pb({b[i],1}); sort(v.begin(),v.end()); dp[0]=0; ll last=0,d=0,sum=0; for(int i=1;i<v.size();i++) { dp[i]=INF; if(v[i-1].S!=v[i].S) { ll tmp=0,cur=i-1; while(v[cur].S==v[i-1].S) { tmp+=v[i].F-v[cur].F; //cout<<cur<<":"<<tmp<<"&"<<dp[cur]<<"&"<<dp[cur-1]<<" "; dp[i]=min({dp[i],dp[cur]+tmp,dp[cur-1]+tmp}); cur--; } last=i-1,d=1,sum=v[i].F-v[i-1].F; } else { dp[i]=dp[i-1]+v[i].F-v[last].F; if(v[last].S==v[last-d].S) { sum+=v[i].F-v[last-d].F; dp[i]=min(dp[i],dp[last-d-1]+sum),d++; } } //cout<<dp[i]<<"\n"; } return dp[v.size()-1]; } /*int main() { ll n,m; cin>>n>>m; vector<int> a(n),b(m); rep(i,n) cin>>a[i]; rep(i,m) cin>>b[i]; cout<<min_total_length(a,b); } */

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<r.size();i++) v.pb({r[i],0});
      |                 ~^~~~~~~~~
wiring.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<b.size();i++) v.pb({b[i],1});
      |                 ~^~~~~~~~~
wiring.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~
wiring.cpp:19:8: warning: unused variable 'lastr' [-Wunused-variable]
   19 |     ll lastr=-INF,lastb=-INF,posr=-1,posb=-1;
      |        ^~~~~
wiring.cpp:19:19: warning: unused variable 'lastb' [-Wunused-variable]
   19 |     ll lastr=-INF,lastb=-INF,posr=-1,posb=-1;
      |                   ^~~~~
wiring.cpp:19:30: warning: unused variable 'posr' [-Wunused-variable]
   19 |     ll lastr=-INF,lastb=-INF,posr=-1,posb=-1;
      |                              ^~~~
wiring.cpp:19:38: warning: unused variable 'posb' [-Wunused-variable]
   19 |     ll lastr=-INF,lastb=-INF,posr=-1,posb=-1;
      |                                      ^~~~
#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...