結果
問題 | No.1736 Princess vs. Dragoness |
ユーザー | O2MT |
提出日時 | 2021-11-24 18:48:23 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 4,333 bytes |
コンパイル時間 | 16,761 ms |
コンパイル使用メモリ | 146,864 KB |
実行使用メモリ | 162,712 KB |
最終ジャッジ日時 | 2023-09-09 11:31:40 |
合計ジャッジ時間 | 21,284 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
28,616 KB |
testcase_01 | AC | 52 ms
28,876 KB |
testcase_02 | AC | 53 ms
28,796 KB |
testcase_03 | AC | 55 ms
29,132 KB |
testcase_04 | AC | 54 ms
28,820 KB |
testcase_05 | AC | 54 ms
29,212 KB |
testcase_06 | AC | 56 ms
29,440 KB |
testcase_07 | AC | 55 ms
29,564 KB |
testcase_08 | AC | 55 ms
29,180 KB |
testcase_09 | AC | 56 ms
31,136 KB |
testcase_10 | AC | 52 ms
28,676 KB |
testcase_11 | AC | 56 ms
29,404 KB |
testcase_12 | AC | 55 ms
29,232 KB |
testcase_13 | AC | 55 ms
29,556 KB |
testcase_14 | AC | 56 ms
29,572 KB |
testcase_15 | AC | 55 ms
29,132 KB |
testcase_16 | AC | 55 ms
29,400 KB |
testcase_17 | AC | 56 ms
31,384 KB |
testcase_18 | AC | 56 ms
29,496 KB |
testcase_19 | AC | 56 ms
29,316 KB |
testcase_20 | AC | 55 ms
29,080 KB |
testcase_21 | AC | 54 ms
29,200 KB |
testcase_22 | AC | 55 ms
29,440 KB |
testcase_23 | AC | 55 ms
29,020 KB |
testcase_24 | AC | 54 ms
28,920 KB |
testcase_25 | AC | 53 ms
29,132 KB |
testcase_26 | AC | 54 ms
29,180 KB |
testcase_27 | AC | 55 ms
29,128 KB |
testcase_28 | AC | 54 ms
29,384 KB |
testcase_29 | AC | 54 ms
29,228 KB |
testcase_30 | AC | 55 ms
29,500 KB |
testcase_31 | AC | 55 ms
30,948 KB |
testcase_32 | AC | 54 ms
29,084 KB |
testcase_33 | AC | 52 ms
28,648 KB |
testcase_34 | AC | 52 ms
28,756 KB |
testcase_35 | AC | 51 ms
162,712 KB |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 136 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(); var PQ = new PriorityQueue<long>((int)N); H.ForEach(PQ.Push); for (int i = 0; i < A && PQ.Count > 0; i++) { var num = PQ.Pop(); if (num - X > 0) { PQ.Push(num - X); } } for (int i = 0; i < B; i++) { var YY = Y; var list = new List<long>(); while (YY > 0 && PQ.Count > 0) { var num = PQ.Pop(); if (num > YY) { list.Add(num - YY); } YY -= num; } list.ForEach(PQ.Push); } if (PQ.Count > 0) { Console.WriteLine("No"); } else { Console.WriteLine("Yes"); } } } 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; } } }