結果
問題 | No.952 危険な火薬庫 |
ユーザー | 👑 hos.lyric |
提出日時 | 2019-12-15 00:19:37 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 306 ms / 2,000 ms |
コード長 | 3,485 bytes |
コンパイル時間 | 901 ms |
コンパイル使用メモリ | 109,068 KB |
実行使用メモリ | 157,124 KB |
最終ジャッジ日時 | 2023-09-04 03:58:55 |
合計ジャッジ時間 | 5,269 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 220 ms
102,456 KB |
testcase_04 | AC | 220 ms
100,704 KB |
testcase_05 | AC | 178 ms
99,700 KB |
testcase_06 | AC | 266 ms
152,548 KB |
testcase_07 | AC | 94 ms
56,952 KB |
testcase_08 | AC | 305 ms
154,688 KB |
testcase_09 | AC | 306 ms
156,988 KB |
testcase_10 | AC | 121 ms
58,572 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 130 ms
66,488 KB |
testcase_13 | AC | 135 ms
69,768 KB |
testcase_14 | AC | 33 ms
18,552 KB |
testcase_15 | AC | 196 ms
99,912 KB |
testcase_16 | AC | 44 ms
27,768 KB |
testcase_17 | AC | 34 ms
18,592 KB |
testcase_18 | AC | 59 ms
31,768 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 3 ms
4,380 KB |
testcase_21 | AC | 116 ms
58,596 KB |
testcase_22 | AC | 29 ms
18,608 KB |
testcase_23 | AC | 3 ms
4,376 KB |
testcase_24 | AC | 12 ms
7,164 KB |
testcase_25 | AC | 261 ms
157,124 KB |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } // floor(a / b) Int divFloor(Int)(Int a, Int b) { return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0); } // ceil(a / b) Int divCeil(Int)(Int a, Int b) { return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0); } enum INF = 10L^^18; // a/b vs c/d int cmp(long a, long b, long c, long d) { const x = divFloor(a, b); const y = divFloor(c, d); if (x != y) return (x < y) ? -1 : (x > y) ? +1 : 0; a -= b * x; c -= d * y; if (b < 0) { a *= -1; b *= -1; } if (d < 0) { c *= -1; d *= -1; } return (a * d < c * b) ? -1 : (a * d > c * b) ? +1 : 0; } void main() { try { for (; ; ) { const N = readInt(); auto A = new long[N + 2]; foreach (i; 1 .. N + 1) { A[i] = readLong(); } auto S = new long[N + 3]; foreach (i; 0 .. N + 2) { S[i + 1] = S[i] + A[i]; } auto dp = new long[][](N + 1, N + 2); foreach (k; 0 .. N + 1) { dp[k][] = INF; } dp[0][0] = 0; foreach (k; 1 .. N + 1) { /* dp[k][i] = \min_{0<=j<i} (dp[k - 1][j] + (S[i] - S[j + 1])^2) = S[i]^^2 + \min_{0<=j<i} (dp[k - 1][j] + S[j + 1]^2 - 2 S[j + 1] S[i]) (- 2 S[j + 1]): decr */ alias Entry = Tuple!(long, long); long eval(ref Entry e, long x) { return e[0] + e[1] * x; } auto que = new Entry[N + 2]; int head, tail; foreach (i; 1 .. N + 2) { // push i - 1 if (dp[k - 1][i - 1] < INF) { const a0 = dp[k - 1][i - 1] + S[i]^^2; const a1 = -2 * S[i]; for (; tail - head >= 2 && cmp(-(que[tail - 1][0] - que[tail - 2][0]), que[tail - 1][1] - que[tail - 2][1], -(a0 - que[tail - 2][0]), a1 - que[tail - 2][1]) >= 0; --tail) {} que[tail++] = Entry(a0, a1); } for (; tail - head >= 2 && eval(que[head], S[i]) >= eval(que[head + 1], S[i]); ++head) {} if (tail - head >= 1) { dp[k][i] = S[i]^^2 + eval(que[head], S[i]); } } } debug { foreach (k; 0 .. N + 1) { writeln(dp[k]); } } foreach_reverse (k; 1 .. N + 1) { writeln(dp[k][N + 1]); } } } catch (EOFException e) { } }