結果
| 問題 |
No.952 危険な火薬庫
|
| コンテスト | |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-01-13 05:27:26 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,107 bytes |
| コンパイル時間 | 1,854 ms |
| コンパイル使用メモリ | 180,268 KB |
| 実行使用メモリ | 214,052 KB |
| 最終ジャッジ日時 | 2024-12-14 17:13:03 |
| 合計ジャッジ時間 | 50,339 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 TLE * 14 |
ソースコード
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif
using i128 = __int128_t;
istream& operator >>(istream &is, i128 &a) {
int64_t i;
is >> i;
a = i;
return is;
}
ostream& operator <<(ostream &os, i128 a) {
auto i = (int64_t)a;
auto j = (int64_t)(a >> 64);
if (j) os << j;
os << i;
return os;
}
struct LiChaoTree {
using Line = PLL;
struct Node {
Line line;
i128 lx, rx;
Node *l, *r;
Node(Line line, i128 lx, i128 rx)
: lx(lx), rx(rx), line(line), l(nullptr), r(nullptr) {}
};
function<i128(i128, i128)> comp; // maybe min or max
function<bool(i128, i128)> comp_b;
i128 inf, max_x, id_ele;
Line init;
Node *root;
LiChaoTree(function<i128(i128, i128)> comp, i128 inf, i128 arg_max_x,
i128 id_ele, Line init)
: comp(comp), init(init), inf(inf), id_ele(id_ele) {
max_x = 1;
while (max_x < arg_max_x)
max_x *= 2;
comp_b = [&](i128 a, i128 b) { return this->comp(a, b) == a; };
root = new Node(init, 0, max_x);
}
i128 calc_y(Line line, i128 x) {
i128 a, b;
tie(a, b) = line;
return a * x + b;
}
i128 calc_y(Node *node, i128 x) { return calc_y(node->line, x); }
Node *add_line(Line line, Node *node, i128 lx, i128 rx) {
if (node == nullptr)
return new Node(line, lx, rx);
i128 mx = (lx + rx) / 2;
bool lcmp = comp_b(calc_y(line, lx), calc_y(node, lx));
bool mcmp = comp_b(calc_y(line, mx), calc_y(node, mx));
bool rcmp = comp_b(calc_y(line, rx), calc_y(node, rx));
if (lcmp && rcmp) {
node->line = line;
return node;
}
if (!lcmp && !rcmp)
return node;
if (mcmp) {
swap(line, node->line);
lcmp = !lcmp;
rcmp = !rcmp;
}
if (lcmp) {
auto l = node->l;
node->l = add_line(line, l, lx, mx);
} else {
auto r = node->r;
node->r = add_line(line, r, mx, rx);
}
return node;
}
Node *add_line_seg(Line line, Node *cur, i128 qlx, i128 qrx, i128 lx,
i128 rx) {
if (cur == nullptr)
cur = new Node(init, lx, rx);
if (qrx <= cur->lx || cur->rx <= qlx)
return cur;
if (qlx <= cur->lx && cur->rx <= qrx)
return add_line(line, cur, lx, rx);
auto mx = (lx + rx) / 2;
cur->l = add_line_seg(line, cur->l, qlx, qrx, lx, mx);
cur->r = add_line_seg(line, cur->r, qlx, qrx, mx, rx);
return cur;
}
Node *add_line(Line line) { return add_line(line, root, 0, max_x); }
Node *add_line(i128 a, i128 b) { return add_line(Line(a, b)); }
Node *add_line_seg(Line line, i128 qlx, i128 qrx) {
return add_line_seg(line, root, qlx, qrx, 0, max_x);
}
i128 query(i128 qx) {
i128 lx = 0, rx = max_x;
Node *cur = root;
i128 ret = id_ele;
while (cur != nullptr) {
i128 tmp = calc_y(cur, qx);
ret = comp(ret, tmp);
if (rx - lx == 1)
break;
i128 mx = (lx + rx) / 2;
if (lx <= qx && qx < mx) {
rx = mx;
cur = cur->l;
} else {
lx = mx;
cur = cur->r;
}
}
return ret;
}
};
const i128 inf = 1e20;
int main() {
ll N;
cin >> N;
V<ll> A(N);
for (ll &e : A) cin >> e;
V<ll> sum(N + 1);
for (ll i = 0; i < N; i++) sum[i + 1] = sum[i] + A[i];
auto dp = make_v<i128>(inf, N + 10, N + 10);
auto pow2 = [](i128 i) { return i * i; };
dp[0][0] = 0;
for (ll i = 1; i <= N + 1; i++) {
dp[i][i - 1] = pow2(sum[i - 1]);
dp[i][0] = 0;
}
for (ll i = 2; i <= N + 1; i++) {
LiChaoTree lct([](i128 a, i128 b) { return min(a, b); }, inf, inf, inf, PLL(inf, inf));
lct.add_line(-2 * sum[i - 1], pow2(sum[i - 1]));
for (ll j = 0; i + j + 1 <= N + 1; j++) {
dp[i + j + 1][j + 1] = min(dp[i + j][j + 1], lct.query(sum[i + j]) + pow2(sum[i + j]));
lct.add_line(-2 * sum[i + j], pow2(sum[i + j]) + dp[i + j][j + 1]);
}
}
for (ll i = 1; i <= N; i++) cout << dp[N + 1][i] << endl;
return 0;
}