結果
| 問題 |
No.952 危険な火薬庫
|
| コンテスト | |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-01-13 05:47:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,859 bytes |
| コンパイル時間 | 1,644 ms |
| コンパイル使用メモリ | 169,452 KB |
| 最終ジャッジ日時 | 2024-11-14 22:01:04 |
| 合計ジャッジ時間 | 2,055 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function 'i128 ConvexHullTrick::get_query(i128)':
main.cpp:117:23: error: call of overloaded 'abs(i128)' is ambiguous
117 | while (2 < abs(right_p - left_p)) {
| ~~~^~~~~~~~~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/cmath:47,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
from main.cpp:2:
/usr/include/stdlib.h:848:12: note: candidate: 'int abs(int)'
848 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
79 | abs(long double __x)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
75 | abs(float __x)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
71 | abs(double __x)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
61 | abs(long long __x) { return __builtin_llabs (__x); }
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
56 | abs(long __i) { return __builtin_labs(__i); }
| ^~~
ソースコード
// #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;
}
const i128 inf = 1e20;
struct ConvexHullTrick {
using Line = pair<i128, i128>;
V<Line> lines;
bool checked;
ConvexHullTrick() : lines(0), checked(false) {}
void update_query(Line l) {
checked = false;
lines.push_back(l);
}
void update_query(i128 a, i128 b) {
update_query(Line(a, b));
}
bool is_necessary(Line a, Line b, Line c) {
if (a < c) swap(a, c);
i128 v1 = (c.second - b.second) * (b.first - a.first);
i128 v2 = (b.second - a.second) * (c.first - b.first);
return v1 < v2;
}
void add_line(i128 a, i128 b) { add_line(Line(a, b)); }
void add_line(PLL c) {
while (lines.size() >= 2) {
auto a = *(lines.end() - 2);
auto b = *(lines.end() - 1);
if (!is_necessary(a, b, c)) {
lines.pop_back();
} else {
break;
}
}
lines.push_back(c);
}
void check_lines() {
checked = true;
sort(ALLR(lines));
auto tmp = lines;
lines.clear();
lines.push_back(tmp[0]);
lines.push_back(tmp[1]);
for (i128 i = 2; i < tmp.size(); i++) {
add_line(tmp[i]);
}
}
i128 get_value(i128 idx, i128 x) {
if (lines.size() <= idx) return inf;
i128 a, b;
tie(a, b) = lines[idx];
return a * x + b;
}
i128 get_query(i128 x) {
/*
if (!checked) {
check_lines();
}
*/
i128 left_p = 0, right_p = (ll)lines.size() - 1;
while (2 < abs(right_p - left_p)) {
auto mid = (left_p + right_p) / 2;
auto f1 = get_value(mid, x);
auto f2 = get_value(mid + 1, x);
if (f1 < f2) right_p = mid;
else left_p = mid;
}
return var_min(get_value(left_p, x),
get_value(left_p + 1, x),
get_value(left_p + 2, x));
}
};
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++) {
ConvexHullTrick cht;
cht.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], cht.get_query(sum[i + j]) + pow2(sum[i + j]));
cht.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;
}