結果
問題 | No.952 危険な火薬庫 |
ユーザー |
👑 ![]() |
提出日時 | 2019-12-01 09:12:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 1,135 ms |
コンパイル使用メモリ | 77,288 KB |
最終ジャッジ日時 | 2025-01-08 06:34:32 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <deque> #include <iostream> using namespace std; using ll = long long; const ll INF = 1e18; struct ConvexHullTrick { using F = pair<ll, ll>; deque<F> deq; #define a first #define b second #define lines deq.size() bool invalid_f1(F f0, F f1, F f2) { return __int128_t(f1.a - f0.a) * (f2.b - f1.b) >= __int128_t(f1.b - f0.b) * (f2.a - f1.a); } ll f(F f0, ll x) { return f0.a * x + f0.b; } void add(F f0) { while (lines >= 2 && invalid_f1(deq[lines - 2], deq[lines - 1], f0)) { deq.pop_back(); } deq.push_back(f0); } ll min(ll x) { while (lines >= 2 && f(deq[0], x) >= f(deq[1], x)) { deq.pop_front(); } return f(deq[0], x); } }; int main() { int N; cin >> N; ll S[N + 1], DP[N + 2][N + 1]; S[0] = 0; for (int i = 0; i < N; i++) cin >> S[i + 1], S[i + 1] += S[i]; for (int i = 0; i < N + 2; i++) { for (int j = 0; j < N + 1; j++) DP[i][j] = INF; } for (int i = 0; i < N + 2; i++) DP[i][0] = 0; for (int i = 0; i < N + 2; i++) { ConvexHullTrick CHT; for (int j = 0; j < N + 1; j++) { if (i + j + 1 > N + 1) break; ll A = -2 * S[i + j], B = S[i + j] * S[i + j] + DP[i + j][j]; ll X = S[i + j], Y = S[i + j] * S[i + j]; CHT.add(make_pair(A, B)); DP[i + j + 1][j] = min(DP[i + j + 1][j], CHT.min(X) + Y); } } for (int i = 0; i < N; i++) { cout << min(DP[N][i + 1], DP[N + 1][i + 1]) << endl; } }