이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(v) v.begin(), v.end()
const int N = 2e5 + 10;
ll pref[N];
ll dp[N];
ll min_total_length(vector<int> r, vector<int> b) {
vector<pair<ll,ll> > A;
A.pb({0, -1});
for(auto u : r)A.pb({u, -1});
for(auto u : b)A.pb({u, 1});
sort(all(A));
int n = A.size();
int cnt = 0;
map<int,int> mp;
for(int i= 1;i<n;i++){
pref[i] = pref[i-1] + A[i].first * A[i].second;
cnt += A[i].second;
ll dist = 1e18;
if(A[i].second == -1){
auto it = lower_bound(all(b), A[i].first);
if(it != b.end())dist = min(dist, *it - A[i].first);;
if(it != b.begin()){
it --;
dist = min(dist, abs(*it - A[i].first));
}
}else{
auto it = lower_bound(all(r), A[i].first);
if(it != r.end())dist = min(dist, *it - A[i].first);;
if(it != r.begin()){
it --;
dist = min(dist, abs(*it - A[i].first));
}
}
dp[i] = dp[i-1] + dist;
if(cnt == 0 || mp[cnt] > 0)dp[i] = min(dp[i], dp[mp[cnt]] + abs(pref[i] - pref[mp[cnt]]));
mp[cnt] = i;
}
return dp[n-1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |