제출 #749833

#제출 시각아이디문제언어결과실행 시간메모리
749833grogu전선 연결 (IOI17_wiring)C++14
0 / 100
1 ms212 KiB
#include "wiring.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; #define maxn 200005 ll n; pll a[maxn]; ll last[2]; ll dp[maxn]; ll ps[maxn]; ll sum = 0; bool ok; long long min_total_length(std::vector<int> r, std::vector<int> b) { for(ll x : r) a[++n] = {x,0}; for(ll x : b) a[++n] = {x,1}; sort(a+1,a+1+n); a[0].sc = 2; sum = 0; for(ll i = 1;i<=n;i++){ if(!last[a[i].sc^1]) continue; if(a[i].sc!=a[i-1].sc){ dp[i] = dp[i-1] + a[i].fi - a[i-1].fi; ll cur = 0; for(ll j = i-1;j>last[a[i].sc];j--){ cur+=a[i].fi-a[j].fi; ps[j] = dp[j-1] + cur; } for(ll j = last[a[i].sc]+2;j<i;j++) ps[j] = min(ps[j],ps[j-1]); dp[i] = min(dp[i],ps[i-1]); ok = 1; sum = 0; }else{ dp[i] = dp[i-1] + a[i].fi - a[last[a[i].sc^1]].fi; sum+= a[i].fi - a[last[a[i].sc^1]+1].fi; ll sz = i-last[a[i].sc^1]; if(ok&&(a[i].sc^1)==a[last[a[i].sc^1]-sz+1].sc){ dp[i] = min(dp[i],ps[last[a[i].sc^1]-sz+1] + sum); }else ok = 0; } last[a[i].sc] = i; } return dp[n]; } /** 4 5 1 2 3 7 0 4 5 9 10 **/
#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...