結果
問題 | No.1739 Princess vs. Dragoness (& AoE) |
ユーザー | O2MT |
提出日時 | 2021-11-24 19:20:52 |
言語 | C# (.NET 7.0.402) |
結果 |
AC
|
実行時間 | 2,249 ms / 3,000 ms |
コード長 | 5,008 bytes |
コンパイル時間 | 9,192 ms |
コンパイル使用メモリ | 146,876 KB |
実行使用メモリ | 163,648 KB |
最終ジャッジ日時 | 2023-09-09 12:07:35 |
合計ジャッジ時間 | 44,041 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
29,056 KB |
testcase_01 | AC | 60 ms
29,184 KB |
testcase_02 | AC | 57 ms
29,060 KB |
testcase_03 | AC | 56 ms
29,028 KB |
testcase_04 | AC | 1,407 ms
55,440 KB |
testcase_05 | AC | 2,249 ms
59,724 KB |
testcase_06 | AC | 212 ms
53,756 KB |
testcase_07 | AC | 57 ms
29,248 KB |
testcase_08 | AC | 667 ms
42,100 KB |
testcase_09 | AC | 811 ms
50,556 KB |
testcase_10 | AC | 702 ms
43,624 KB |
testcase_11 | AC | 416 ms
40,352 KB |
testcase_12 | AC | 65 ms
35,608 KB |
testcase_13 | AC | 844 ms
46,808 KB |
testcase_14 | AC | 1,474 ms
53,072 KB |
testcase_15 | AC | 1,247 ms
50,216 KB |
testcase_16 | AC | 1,051 ms
41,696 KB |
testcase_17 | AC | 626 ms
42,936 KB |
testcase_18 | AC | 1,104 ms
45,068 KB |
testcase_19 | AC | 186 ms
43,792 KB |
testcase_20 | AC | 303 ms
39,024 KB |
testcase_21 | AC | 545 ms
50,104 KB |
testcase_22 | AC | 1,188 ms
51,080 KB |
testcase_23 | AC | 1,245 ms
50,128 KB |
testcase_24 | AC | 2,197 ms
57,476 KB |
testcase_25 | AC | 1,940 ms
60,264 KB |
testcase_26 | AC | 1,407 ms
51,904 KB |
testcase_27 | AC | 2,134 ms
57,340 KB |
testcase_28 | AC | 1,458 ms
55,448 KB |
testcase_29 | AC | 2,183 ms
59,308 KB |
testcase_30 | AC | 1,552 ms
55,608 KB |
testcase_31 | AC | 1,607 ms
58,516 KB |
testcase_32 | AC | 2,213 ms
58,044 KB |
testcase_33 | AC | 60 ms
28,988 KB |
testcase_34 | AC | 60 ms
29,292 KB |
testcase_35 | AC | 59 ms
29,012 KB |
testcase_36 | AC | 61 ms
29,048 KB |
testcase_37 | AC | 60 ms
29,188 KB |
testcase_38 | AC | 61 ms
29,652 KB |
testcase_39 | AC | 64 ms
29,888 KB |
testcase_40 | AC | 61 ms
29,540 KB |
testcase_41 | AC | 63 ms
29,620 KB |
testcase_42 | AC | 62 ms
163,648 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 130 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Linq; namespace Sample { class Program { static void Main(string[] args) { var arr = Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); var (N, A, B, X, Y) = (arr[0], arr[1], arr[2], arr[3], arr[4]); var H = Console.ReadLine().Split(' ').Select(long.Parse).ToList(); // 汎用的な二分探索のテンプレ long binary_search(List<long> H) { long ng = -1; long ok = (long)Math.Pow(10, 18); /* ok と ng のどちらが大きいかわからないことを考慮 */ while (Math.Abs(ok - ng) > 1) { long mid = (ok + ng) / 2; if (isClearedAllMonsters(H, mid)) ok = mid; else ng = mid; } return ok; } bool isClearedAllMonsters(List<long> H, long k) { var PQ = new PriorityQueue<long>((int)N); foreach (var h in H) { if (h - k > 0) PQ.Push(h - k); } if (PQ.Count == 0) { return true; } for (int i = 0; i < A && PQ.Count > 0; i++) { var num = PQ.Pop(); if (num - X > 0) { PQ.Push(num - X); } } var list = PQ.GetAllElements().ToList(); long allHP = 0; list.ForEach(x => allHP += x); if (B * Y >= allHP) { return true; } else { return false; } } var ans = binary_search(H); Console.WriteLine(ans); } } class PriorityQueue<T> where T : IComparable<T> { private readonly T[] _array; private readonly IComparer _comparer; public int Count { get; private set; } = 0; public T Root => _array[0]; public PriorityQueue(int capacity, IComparer comparer = null) { _array = new T[capacity]; _comparer = comparer; } /// <summary> /// 要素を挿入する /// </summary> /// public void Push(T item) { _array[this.Count] = item; Count += 1; var n = Count - 1; // 末尾(追加した)のノードの番号 while (n != 0) { var parent = (n - 1) / 2; // 親ノードの番号 if (Compare(_array[n], _array[parent]) > 0) { Swap(n, parent); n = parent; } else { break; } } } /// <summary> /// 優先度の一番高いものを取り出す /// </summary> public T Pop() { Swap(0, this.Count - 1); // 先頭要素を末尾にする Count -= 1; var parent = 0; // 親ノードの番号 while (true) { var child = 2 * parent + 1; // 子ノードの番号 if (child > Count - 1) break; // 値の大きい方の子を選ぶ if (child < Count - 1 && Compare(_array[child], _array[child + 1]) < 0) child += 1; // 子の方が親より大きければ入れ替える if (Compare(_array[parent], _array[child]) < 0) { Swap(parent, child); parent = child; } else { break; } } return _array[Count]; } /// <summary> /// 大きいものから列挙していく /// withPop = falseのときは順番関係なく取り出しもしないが素早く全要素を取得できる /// </summary> public IEnumerable<T> GetAllElements(bool withPop = true) { int count = Count; for (int i = 0; i < count; i++) { if (withPop) yield return Pop(); else yield return _array[count - i - 1]; } } private int Compare(T a, T b) { if (_comparer == null) return a.CompareTo(b); return _comparer.Compare(a, b); } private void Swap(int a, int b) { var tmp = _array[a]; _array[a] = _array[b]; _array[b] = tmp; } } }