이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
#include "wiring.h"
LL min_total_length(vector<int> r, vector<int> b) {
vector<PII> p = {{-1, -1}};
for(int x : r) p.emplace_back(x, 1);
for(int x : b) p.emplace_back(x, 2);
sort(p.begin(), p.end());
int n = size(p) - 1;
LL inf = 1e18;
vector<LL> sum(n + 1), dp(n + 1, inf);
dp[0] = 0;
FOR(i, 1, n) sum[i] = sum[i - 1] + p[i].ST;
auto get = [&](int l, int s, int r) {
LL ret = sum[r] - 2 * sum[s] + sum[l - 1] + dp[l - 1];
r = r - s, l = s - l + 1;
if(l < r) ret -= LL(r - l) * p[s].ST;
else ret += LL(l - r) * p[s + 1].ST;
return min(ret, inf);
};
int split, ptr;
FOR(i, 1, n) {
if(p[i].ND != p[i - 1].ND)
split = ptr = i - 1;
while(0 < ptr && p[ptr].ND == p[split].ND && get(ptr, split, i) <= dp[i])
dp[i] = get(ptr--, split, i);
if(ptr != split) ptr++;
}
return dp[n];
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'LL min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:68:25: warning: 'ptr' may be used uninitialized in this function [-Wmaybe-uninitialized]
while(0 < ptr && p[ptr].ND == p[split].ND && get(ptr, split, i) <= dp[i])
^
wiring.cpp:64:6: warning: 'split' may be used uninitialized in this function [-Wmaybe-uninitialized]
int split, ptr;
^~~~~
# | 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... |