이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
ll min_total_length(vector<int> r, vector<int> b)
{
/*vector<vector<ll>> dp(r.size(), vector<ll>(b.size()));
for (int i = 0; i < b.size(); ++i)
{
dp[0][i] = abs(r[0] - b[i]);
if (i != 0) dp[0][i] += dp[0][i - 1];
}
for (int i = 1; i < r.size(); ++i)
{
for (int j = 0; j < b.size(); ++j)
{
dp[i][j] = dp[i - 1][j] + abs(r[i] - b[j]);
if (j != 0)
{
dp[i][j] = min({dp[i][j], dp[i][j - 1] + abs(r[i] - b[j]),
dp[i - 1][j - 1] + abs(r[i] - b[j])});
}
}
}
return dp.back().back();*/
vector<pair<ll, bool>> points;
for (int i : r) points.emplace_back(i, 0);
for (int i : b) points.emplace_back(i, 1);
sort(points.begin(), points.end());
int n = points.size();
vector<ll> dp(n, 1e18);
multiset<ll> prev, prevCh;
vector<ll> cur, help, bruh{0};
cur.push_back(0); //change maybe later
ll sum = 0, sumPrev = 0, sumCur = 0;
ll cntPrev = 0, cntCur = 1;
for (int i = 1; i < n; ++i)
{
if (points[i].second != points[i - 1].second)
{
cntPrev = cntCur;
cntCur = 0;
sumPrev = sumCur;
sumCur = sum = 0;
prev.clear();
prevCh.clear();
ll tmp = 0;
reverse(cur.begin(), cur.end());
for (int j = 0; j < cur.size(); ++j)
{
tmp += points[i - 1].first - points[i - 1 - j].first;
cur[j] += tmp;//sumPrev - bruh[j];
prev.insert(cur[j] + (j + 1) * (points[i].first - points[i - 1].first));
}
help = cur;
cur.clear();
bruh.clear();
//change
//add delta
}
//do addition
++cntCur;
sum += points[i].first - points[i - cntCur + 1].first;
sumCur += (cntCur - 1) * (points[i].first - points[i - 1].first);
bruh.push_back(sumCur);
cur.push_back(dp[i - 1]);
//change in prev because cntCur > cnt there
if (prev.empty() && prevCh.empty()) continue;
dp[i] = dp[i - cntCur] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first) + sum;
if (!prev.empty()) dp[i] = min(dp[i], *prev.begin() + sum);
if (!prevCh.empty()) dp[i] = min(dp[i], *prevCh.begin() + sum + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first));
if (!prev.empty())
{
prev.erase(prev.find(help[cntCur - 1] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first)));
prevCh.insert(help[cntCur - 1]);
}
/*
6 2
602 608 638 642 649 650
214 220
*/
/*int last;
ll sum = 0, cnt = 1;
for (last = i - 1; last >= 0 && points[last].second == points[i].second; --last)
{
sum += (points[last + 1].first - points[last].first) * (i - last);
++cnt;
}
if (last < 0) continue;
dp[i] = dp[last] + sum + cnt * (points[last + 1].first - points[last].first);
int st = last;
ll sum2 = 0;
for (; last >= 0 && points[last].second != points[i].second; --last)
{
sum2 += points[st].first - points[last].first;
ll res = sum2 + sum + max(cnt, st - last + 1ll) * (points[st + 1].first - points[st].first);
if (last > 0) res += dp[last - 1];
dp[i] = min(dp[i], res);
}*/
}
return dp.back();
}
/*
6 6
0 6 20 23 43 44
52 54 70 87 88 101
*/
/*
20 20
231 257 258 364 378 454 496 545 601 602 608 631 638 642 649 650 695 736 786 3784
25 79 112 125 143 145 160 190 193 194 214 220 2390 2428 2460 2473 2481 2510 3785 3850
*/
/*
9 3
602 608 638 642 649 650 695 786 3784
214 220 3785
*/
/*
6 2
602 608 638 642 649 650
214 220
*/
//dp[9] - first wrong
// 0 1 2 3 4 5 6 7 8 9
//correct inf inf inf inf 10 11 13 16 14 15
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int j = 0; j < cur.size(); ++j)
| ~~^~~~~~~~~~~~
wiring.cpp:41:17: warning: variable 'sumPrev' set but not used [-Wunused-but-set-variable]
41 | ll sum = 0, sumPrev = 0, sumCur = 0;
| ^~~~~~~
wiring.cpp:42:8: warning: variable 'cntPrev' set but not used [-Wunused-but-set-variable]
42 | ll cntPrev = 0, cntCur = 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... |