제출 #1025645

#제출 시각아이디문제언어결과실행 시간메모리
1025645parsadox2전선 연결 (IOI17_wiring)C++17
0 / 100
18 ms7040 KiB
#include "wiring.h" #include <bits/stdc++.h> #define F first #define S second using namespace std; const int N = 1e5 + 10; const long long inf = 1e18; int a[N] , col[N] , n; long long dp[N]; void Solve(int id) { int las1 = 1 , las2 = 1 , cnt1 = 0 , cnt2 = 0; for(int i = id ; i > 0 ; i--) { if(col[i] != col[id]) { las1 = i + 1; break; } cnt1++; } for(int i = las1 - 1 ; i > 0 ; i--) { if(col[i] != col[las1 - 1]) { las2 = i + 1; break; } cnt2++; } //cout << id << " " << cnt1 << " " << las1 << " " << cnt2 << " " << las2 << endl; if(cnt2 == 0) { dp[id] = inf; return; } if(cnt1 >= cnt2) { dp[id] = min(dp[las2 - 1] , dp[las2]); for(int i = id ; i >= las2 ; i--) dp[id] += (col[i] == col[id] ? a[i] : -a[i]); dp[id] -= 1LL * (cnt1 - cnt2) * a[las1 - 1]; return; } for(int i = 0 ; i < cnt1 ; i++) { dp[id] += (a[id - i] - a[las1 - 1 - i]); } long long val = inf , sum = 0; for(int i = las1 - cnt1 - 1 ; i >= las2 ; i--) { val = min(val , sum + dp[i]); sum += (a[las1] - a[i]); } val = min(val , sum + dp[las2 - 1]); dp[id] += val; return; } long long min_total_length(vector<int> r, vector<int> b) { n = r.size() + b.size(); vector <pair<int , int>> vec; for(auto u : r) vec.push_back({u , 0}); for(auto u : b) vec.push_back({u , 1}); sort(vec.begin() , vec.end()); for(int i = 1 ; i <= n ; i++) { a[i] = vec[i - 1].F; col[i] = vec[i - 1].S; } dp[0] = 0; for(int i = 1 ; i <= n ; i++) Solve(i); return dp[n]; }
#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...