이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;
using ll = long long;
vector<pair<ll, bool>> nodes;
vector<ll> prevDiff, nextDiff;
vector<ll> matchRMemo;
ll matchR(ll i) {
if (matchRMemo[i] != -1)
return matchRMemo[i];
ll dst = nextDiff[i] - i;
ll midx = nextDiff[i] + dst - 1;
if (midx >= nextDiff[nextDiff[i]])
midx = nextDiff[i];
ll ans = nodes[midx].first - nodes[i].first;
if (i + 1 != nodes.size() && nodes[i + 1].second == nodes[i].second)
ans += matchR(i + 1);
//cout << "MR @" << i << " = " << ans << "\n";
return matchRMemo[i] = ans;
}
vector<ll> memo;
ll dp(ll i) {
if (i >= memo.size())
return 0;
if (memo[i] != -1)
return memo[i];
ll ans = LLONG_MAX;
if (nextDiff[i] != nodes.size()) { // match right
ll dst = nextDiff[i] - i;
ll nidx = min(nextDiff[i] + dst, nextDiff[nextDiff[i]]);
ans = min(ans, dp(nidx) + matchR(i));
}
if (prevDiff[i] != -1) { // match left
ans = min(ans, dp(i + 1) + nodes[i].first - nodes[prevDiff[i]].first);
}
return memo[i] = ans;
}
ll min_total_length(std::vector<int> r, std::vector<int> b) {
for (int x : r)
nodes.emplace_back(x, true);
for (int x : b)
nodes.emplace_back(x, false);
sort(all(nodes));
prevDiff.resize(nodes.size(), -1);
for (ll i = 1; i < nodes.size(); i++) {
if (nodes[i].second == nodes[i - 1].second)
prevDiff[i] = prevDiff[i - 1];
else
prevDiff[i] = i - 1;
}
nextDiff.resize(nodes.size() + 1, nodes.size());
for (ll i = nodes.size() - 2; i >= 0; i--) {
if (nodes[i].second == nodes[i + 1].second)
nextDiff[i] = nextDiff[i + 1];
else
nextDiff[i] = i + 1;
}
//for (ll x : distL)
// cout << x << " ";
//cout << "\n";
matchRMemo.resize(nodes.size(), -1);
memo.resize(nodes.size(), -1);
return dp(0);
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'll matchR(ll)':
wiring.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 != nodes.size() && nodes[i + 1].second == nodes[i].second)
~~~~~~^~~~~~~~~~~~~~~
wiring.cpp: In function 'll dp(ll)':
wiring.cpp:33:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i >= memo.size())
~~^~~~~~~~~~~~~~
wiring.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (nextDiff[i] != nodes.size()) { // match right
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll i = 1; i < nodes.size(); i++) {
~~^~~~~~~~~~~~~~
# | 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... |