結果
問題 | No.1906 Twinkle Town |
ユーザー |
👑 |
提出日時 | 2022-04-15 22:39:44 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 4,241 bytes |
コンパイル時間 | 2,441 ms |
コンパイル使用メモリ | 191,308 KB |
実行使用メモリ | 14,124 KB |
最終ジャッジ日時 | 2024-06-22 14:56:03 |
合計ジャッジ時間 | 9,467 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
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)); }void experimentUso() {foreach (n; 1 .. 6 + 1) {// want at least as good as pforeach (p; 0 .. 1 << n) {auto dp0 = new bool[][](1 << n, 1 << n);auto dp1 = new bool[][](1 << n, 1 << n);foreach (r; 0 .. 1 << n) {((!(p & ~r)) ? dp1[0][r] : dp0[0][r]) = true;}foreach (q; 1 .. 1 << n) foreach (r; 0 .. 1 << n) {foreach (i; 0 .. n) if (q & 1 << i) {const qq = q ^ 1 << i;const move = (1 << (i + 1)) - 1;if (!dp1[qq][r & ~move]) dp0[q][r] = true;if (!dp0[qq][r | move]) dp1[q][r] = true;}}if (dp1[(1 << n) - 1][0]) {writeln(iota(n).map!(i => "01"[p >> i & 1]));}}}}enum INF = 10L^^18;long brute(const(long[]) B) {const N = cast(int)(B.length);auto dp = new long[][](1 << N, 1 << N);foreach (i; 0 .. N) {foreach (r; 0 .. 1 << i) {dp[0][r | 1 << i] = dp[0][r] + B[i];}}foreach (q; 1 .. 1 << N) foreach (r; 0 .. 1 << N) {if ((N - popcnt(q)) % 2 == 0) {// 1dp[q][r] = -INF;foreach (i; 0 .. N) if (q & 1 << i) {chmax(dp[q][r], dp[q ^ 1 << i][r | ((1 << (i + 1)) - 1)]);}} else {// 0dp[q][r] = +INF;foreach (i; 0 .. N) if (q & 1 << i) {chmin(dp[q][r], dp[q ^ 1 << i][r & ~((1 << (i + 1)) - 1)]);}}}return dp[$ - 1][0];}long solve(const(long[]) B) {const N = cast(int)(B.length);long ans;if (N % 2 != 0) {ans += B[0];BinaryHeap!(Array!long) que;for (int i = 1; i < N; i += 2) {que.insert(B[i]);que.insert(B[i + 1]);ans += que.front;que.removeFront;}} else {ans += B[N - 1];BinaryHeap!(Array!long, "a > b") que;for (int i = N - 2; i > 0; i -= 2) {que.insert(B[i]);que.insert(B[i - 1]);ans += que.front;que.removeFront;}}return ans;}void experiment() {foreach (n; 1 .. 6 + 1) {auto bs = new long[n];foreach (i; 0 .. n) {bs[i] = 1 << i;}do {const brt = brute(bs);const sol = solve(bs);writeln(bs, ": ", iota(n).map!(i => ((brt & bs[i]) ? '1' : '0')), " ", brt, " ", sol);assert(popcnt(brt) == (n + 1) / 2);if (n % 2 != 0) {assert(brt == sol);} else {assert(brt & bs[n - 1]);assert(brt == sol);}} while (bs.nextPermutation);}}void main() {debug {experiment;}try {for (; ; ) {const numCases = readInt;foreach (caseId; 0 .. numCases) {const N = readInt;auto A = new long[N];foreach (i; 0 .. N) {A[i] = readLong;}A.sort;auto B = A.dup;foreach_reverse (i; 1 .. N) {B[i] -= B[i - 1];}const ans = solve(B);writeln(ans);debug {const brt = brute(B);writeln("B = ", B);writeln("brt = ", brt);}}}} catch (EOFException e) {}}