제출 #137132

#제출 시각아이디문제언어결과실행 시간메모리
137132Mahdi_Jfri전선 연결 (IOI17_wiring)C++14
0 / 100
3 ms1916 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 2e5 + 20; ll dp[maxn]; vector<int> t[2]; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size() + b.size(); vector<pair<int , int> > a; for(auto x : r) a.pb({x , 0}); for(auto x : b) a.pb({x , 1}); a.pb({-1e9 , -1}); sort(a.begin() , a.end()); memset(dp , 63 , sizeof dp); dp[0] = 0; for(int i = 1; i <= n; i++) { t[0].clear() , t[1].clear(); for(int j = i - 1; j >= 0; j--) { t[a[j + 1].second].pb(a[j + 1].first); int shit = min(t[0].size() , t[1].size()); if(shit == 1) { int ind = -1; if((int)t[0].size() == 1) ind = 0; else ind = 1; ll tmp = 0; for(auto x : t[ind ^ 1]) tmp += abs(t[ind][0] - x); dp[i] = min(dp[i] , dp[j] + tmp); } if(t[0].size() == t[1].size()) { ll tmp = 0; for(int j = 0; j < (int)t[0].size(); j++) tmp += abs(t[0][j] - t[1][j]); dp[i] = min(dp[i] , dp[j] + tmp); } } } 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...