이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <random>
using namespace std;
using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;
template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
cerr << "}";
}
template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
print_tuple(t, index_sequence_for<Args...>{});
return os;
}
ostream& operator<<(ostream& os, string& s) {
for (char c : s) os << c;
return os;
}
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
os << "{";
int g = size(o);
for (auto i : o) os << i << ((--g) == 0 ? "" : ", ");
os << "}";
return os;
}
template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
os << "{" << p.f << ", " << p.s << "}";
return os;
}
template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
int i = 0;
while (names[i] != '\0' && names[i] != ',') i++;
constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
if constexpr (is_str) cerr << head; // ignore directly passed strings
else cerr.write(names, i) << " = " << head;
if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
else cerr << endl;
}
#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif
/*
let dp[i][j] to be the min cost of making the i'th tower height j
dp[i][j] = min (j - h <= k <= j + h) dp[i - 1][k] + abs(s[i] - j)
assume the function is convex
then, the min part of the transition is just splitting the function apart at its midpoint and then moving the two halves
left and right by h, keeping it convex
abs(s[i] - j) is also a convex function, meaning convex will stay convex
the function begins as convex, and hence each dp column will always be convex
maintain set of slope changing points as a treap
*/
random_device rd;
mt19937 mt(rd());
using ptr = struct Node*;
struct Node {
ptr l, r;
int pri, sz;
ll k, lazy;
Node(ll k) : k(k) {
pri = mt();
sz = 1;
l = r = 0;
lazy = 0;
}
};
void operator+=(pl& lhs, pl rhs) {
lhs.f += rhs.f;
lhs.s += rhs.s;
}
int sz(ptr n) { return n ? n->sz : 0; }
void push(ptr n) {
if (!n) return;
n->k += n->lazy;
if (n->l) n->l->lazy += n->lazy;
if (n->r) n->r->lazy += n->lazy;
n->lazy = 0;
}
ptr pull(ptr n) {
if (!n) return 0;
push(n->l), push(n->r);
n->sz = sz(n->l) + 1 + sz(n->r);
return n;
}
pair<ptr, ptr> split(ptr n, ll k) {
if (!n) return {0, 0};
push(n);
if (k <= n->k) {
auto [l, r] = split(n->l, k);
n->l = r;
return {l, pull(n)};
} else {
auto [l, r] = split(n->r, k);
n->r = l;
return {pull(n), r};
}
}
pair<ptr, ptr> spliti(ptr n, int i) {
if (!n) return {0, 0};
push(n);
if (i <= sz(n->l)) {
auto [l, r] = spliti(n->l, i);
n->l = r;
return {l, pull(n)};
} else {
auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
n->r = l;
return {pull(n), r};
}
}
ptr merge(ptr l, ptr r) {
if (!l || !r) return max(l, r);
push(l), push(r);
ptr t;
if (l->pri > r->pri) l->r = merge(l->r, r), t = l;
else r->l = merge(l, r->l), t = r;
return pull(t);
}
void ins(ptr& n, ll k) {
auto [l, r] = split(n, k);
n = merge(l, merge(new Node(k), r));
}
void tour(ptr n, int p = 1) {
if (p) cerr << "tour: ";
if (n) {
push(n);
tour(n->l, 0);
cerr << n->k << " ";
tour(n->r, 0);
}
if (p) cerr << endl;
}
main() {
cin.tie(0)->sync_with_stdio(0);
ll n, k; cin >> n >> k;
ptr tree = 0;
pl func = {0, 0};
F0R (_, n) {
ll h; cin >> h;
// spread at min
auto [l, r] = spliti(tree, sz(tree) - func.f);
if (l) l->lazy -= k;
if (r) r->lazy += k;
tree = merge(l, r);
func.s -= k * func.f;
// ditch negative dp values
tie(l, r) = split(tree, 0);
tree = r;
// insert function
F0R (i, 2) ins(tree, h);
// update turning points
func += {1, -h};
}
while (func.f > 0) {
auto [l, r] = spliti(tree, sz(tree) - 1);
tree = l;
ll x = r->k;
ll y = func.f * x + func.s;
func.f--;
func.s = y - x * func.f;
}
cout << func.s << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
safety.cpp:181:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
181 | main() {
| ^~~~
# | 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... |
# | 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... |