結果
問題 | No.952 危険な火薬庫 |
ユーザー | 👑 tatyam |
提出日時 | 2019-12-01 09:12:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 862 ms |
コンパイル使用メモリ | 78,996 KB |
実行使用メモリ | 73,736 KB |
最終ジャッジ日時 | 2023-08-13 10:27:13 |
合計ジャッジ時間 | 4,029 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,384 KB |
testcase_03 | AC | 147 ms
49,828 KB |
testcase_04 | AC | 141 ms
49,104 KB |
testcase_05 | AC | 111 ms
40,016 KB |
testcase_06 | AC | 181 ms
59,044 KB |
testcase_07 | AC | 49 ms
21,904 KB |
testcase_08 | AC | 191 ms
66,676 KB |
testcase_09 | AC | 199 ms
67,712 KB |
testcase_10 | AC | 70 ms
28,252 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 73 ms
29,892 KB |
testcase_13 | AC | 80 ms
31,148 KB |
testcase_14 | AC | 17 ms
9,420 KB |
testcase_15 | AC | 122 ms
44,700 KB |
testcase_16 | AC | 22 ms
11,500 KB |
testcase_17 | AC | 17 ms
9,528 KB |
testcase_18 | AC | 30 ms
14,800 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 68 ms
27,264 KB |
testcase_22 | AC | 13 ms
8,136 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 8 ms
5,480 KB |
testcase_25 | AC | 194 ms
73,736 KB |
ソースコード
#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; } }