Submission #1044576

#TimeUsernameProblemLanguageResultExecution timeMemory
1044576Hugo1729Wiring (IOI17_wiring)C++11
Compilation error
0 ms0 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[200001]={0}; ll pref[200001]={0}; ll min_total_length(vector<ll> r, vector<ll> b) { ll n=r.size(),m=b.size(); vector<pair<ll,ll>> a; for(ll v : r)a.push_back({v,0}); for(ll v : b)a.push_back({v,1}); sort(a.begin(),a.end()); for(ll i=0;i<n+m;i++){ pref[i+1]=pref[i]+a[i].first; } // for(ll i=0;i<n+m;i++)cout << a[i].first << ' '; // cout << '\n'; // for(ll i=0;i<=n+m;i++)cout << pref[i] << ' '; // cout << '\n'; ll prev_begin=-1,prev_end=-1; for(ll i=1;i<n+m;i++){ if(a[i].second!=a[i-1].second){ prev_begin=prev_end+1; prev_end=i-1; } if(prev_begin==-1)continue; if(prev_begin==0){ dp[i]=LLONG_MAX/4; ll x=(prev_end-prev_begin+1),y=i-prev_end; if(x<=y){ dp[i]=(a[prev_end].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y); // cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n'; }else{ dp[i]=(a[prev_end+1].first*x-pref[prev_end+1])+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y); // cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n'; } continue; } dp[i]=LLONG_MAX/4; for(ll j=prev_begin;j<=prev_end;j++){ ll x=(prev_end-j+1),y=i-prev_end; if(x<=y){ dp[i]=min(dp[i],(a[prev_end].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end].first*y)+dp[j-1]); // cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "a: " << (a[prev_end].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end].first*y) << '\n'; }else{ dp[i]=min(dp[i],(a[prev_end+1].first*x-(pref[prev_end+1]-pref[j]))+(pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y)+dp[j-1]); // cout << i << ' ' << prev_begin << ' ' << prev_end << ' ' << "b: " << (a[prev_end+1].first*x-pref[prev_end+1]) << ' ' << (pref[i+1]-pref[prev_end+1]-a[prev_end+1].first*y) << '\n'; } } } // cout << "\n\n"; // for(ll i=0;i<n+m;i++)cout << dp[i] << ' '; // cout << "\n\n"; return dp[n+m-1]; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc0CR8v3.o: in function `main':
grader.cpp:(.text.startup+0x258): undefined reference to `min_total_length(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status