이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pref[100];
int last[100];
ll dp[100];
ll min_total_length(std::vector<int> r, std::vector<int> b)
{
int n = r.size() + b.size();
vector < pair < int , int > > v;
for (int x : r) v.emplace_back(x, 0);
for (int x : b) v.emplace_back(x, 1);
sort(v.begin(), v.end());
pref[0] = v[0].first;
dp[0] = 1ll<<60;
last[0] = -1;
for (int i = 1; i < n; i++)
{
dp[i] = 1ll<<60;
auto [x, t] = v[i];
pref[i] = pref[i-1] + x;
if (v[i-1].second == t) last[i] = last[i-1];
else last[i] = i-1;
if (last[i] == -1) continue;
dp[i] = min(dp[i-1] + x - v[last[i]].first, dp[i]);
if (i - last[i] <= last[i] - last[last[i]])
{
dp[i] = min(dp[i], dp[last[i] - (i - last[i])] + (pref[i] - pref[last[i]]) - (pref[last[i]] - pref[last[i] - (i - last[i])]));
}
/*if (last[last[i]] < last[i] - (i - last[i]) + 1) {
dp[i] = min(dp[i], (pref[i] - pref[last[i]]) - (pref[last[i]] - pref[last[i] - (i - last[i])]) + dp[last[i] - (i - last[i])]);
}*/
//cerr << i << " " << dp[i] << "\n";
}
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... |