結果
問題 | No.952 危険な火薬庫 |
ユーザー |
|
提出日時 | 2019-12-15 00:33:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 439 ms / 2,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 1,752 ms |
コンパイル使用メモリ | 178,460 KB |
実行使用メモリ | 77,952 KB |
最終ジャッジ日時 | 2024-06-28 09:03:43 |
合計ジャッジ時間 | 6,383 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() using i128 = __int128_t; struct CHT { struct point { i128 x, y; point(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {} friend point operator-(point a, point b) { a.x -= b.x; a.y -= b.y; return a; } }; i128 cross(point a, point b) { return (i128)a.x * b.y - (i128)a.y * b.x; } deque<point> H; long long eval(point a, long long x) { return a.x * x + a.y; } void push(long long x, long long y) { point p(x, y); while (H.size() >= 2 && cross(H[H.size() - 1] - H[H.size() - 2], p - H[H.size() - 1]) >= 0) { H.pop_back(); } H.push_back(p); } long long maximum(long long x) { if (H.empty()) return -1e18; while (H.size() >= 2 && eval(H[0], x) <= eval(H[1], x)) H.pop_front(); return eval(H[0], x); } }; int main() { int N; cin >> N; vector<ll> A(N + 1); rep(i, N) cin >> A[i]; vector<ll> S(N + 2); rep(i, N + 1) S[i + 1] = S[i] + A[i]; vector<vector<ll>> dp(N + 2, vector<ll>(N + 2, 1e18)); dp[0][0] = 0; vector<CHT> cht(N + 2); constexpr ll inf = 1e18; cht[0].push(0, 0); for (int i = 0; i <= N; i++) { for (int j = 0; j <= N; j++) { ll v = -cht[j].maximum(S[i]); if (v == inf) continue; dp[i + 1][j + 1] = v + S[i] * S[i]; cht[j + 1].push(2*S[i+1], -dp[i+1][j+1] - S[i+1]*S[i+1]); } } for (int i = N; i >= 1; i--) { cout << dp[N+1][i] << endl; } }