이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
vector<pair<int, int> > v;
const long long INF = 1e17;
long long dp[200010], pref[200010];
int st[200010], en[200010];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size() + b.size();
for(auto &k : r) v.emplace_back(k, 0);
for(auto &k : b) v.emplace_back(k, 1);
v.emplace_back(-1, -1);
sort(v.begin(), v.end());
st[1] = 1;
for(int i = 2; i <= n; i++){
if(v[i].second == v[i - 1].second) st[i] = st[i - 1];
else st[i] = i;
}
en[n] = n;
for(int i = n - 1; i >= 1; i--){
if(v[i].second == v[i + 1].second) en[i] = en[i + 1];
else en[i] = i;
}
for(int i = 1; i <= n; i++){
dp[i] = INF;
pref[i] = pref[i - 1] + v[i].first;
if(en[i] != n) dp[i] = min(dp[i], dp[i - 1] + v[en[i] + 1].first - v[i].first);
if(st[i] == 1) continue;
if(st[i] == i){
dp[i] = min(dp[i], dp[i - 1]);
}
dp[i] = min(dp[i], dp[i - 1] + v[i].first - v[st[i] - 1].first);
int len = i - st[i] + 1;
if(st[i] - st[st[i] - 1] >= len) dp[i] = min(dp[i], dp[st[i] - len - 1] + (pref[i] - pref[st[i] - 1]) - (pref[st[i] - 1] - pref[st[i] - len - 1]));
// cerr << i << " " << dp[i] << "\n";
}
return dp[n];
}
# | 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... |