제출 #284504

#제출 시각아이디문제언어결과실행 시간메모리
284504mohammad전선 연결 (IOI17_wiring)C++14
0 / 100
1 ms384 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; #define endl "\n" // #define int long long typedef long long ll ; const ll ooo = 1e14 ; const ll oo = 2e9 ; const double PI = acos(-1) ; const ll M = 1e9 + 7 ; const int N = 10000010 ; ll dp[200010] , d[200010] , sum[200010]; ll min_total_length(vector<int> r, vector<int> b) { vector<pair<ll,ll>> v; for(auto i : r) v.push_back({i , 0}); for(auto i : b) v.push_back({i , 1}); sort(v.begin(), v.end()); int n = v.size(); sum[0] = v[0].first ; d[0] = -1 ; dp[0] = ooo; for(int i = 1 ; i < n; ++i){ dp[i] = ooo; sum[i] = sum[i - 1] + v[i].first; d[i] = (v[i].second == v[i - 1].second ? d[i - 1] : i - 1); if(d[i] == -1) continue ; // cout << i << ' ' << d[i] << ' ' << d[i] - (i - d[i]) << endl; dp[i] = min(dp[i - 1] + v[i].first - v[d[i]].first , dp[i]); if(d[d[i]] <= d[i] - (i - d[i]) ){ dp[i] = min(dp[i] , (sum[i] - sum[d[i]]) - (sum[d[i]] - sum[d[i] - (i - d[i])]) + dp[d[i] - (i - d[i])]); if(dp[i] == ooo){ ll ds = (d[i] - d[d[i]]) , ds1 = i - d[i]; dp[i] = min(dp[i] , ((sum[i] - sum[d[i]]) - ds1 * v[d[i]+1].first) + (v[d[i]].first * ds - (sum[d[i]] - sum[d[i] - (i - d[i])]) ) + ds * (v[i].first - v[d[i]].first) ); // cout << ds << ' ' << v[d[i]].first << ' ' << v[i].first << endl; } } } return dp[n - 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...