結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 2021-10-09 07:46:15 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,089 ms / 3,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 3,923 ms |
コンパイル使用メモリ | 112,020 KB |
実行使用メモリ | 186,304 KB |
最終ジャッジ日時 | 2024-07-23 18:51:54 |
合計ジャッジ時間 | 6,307 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System.Collections.Generic;using System.Linq;using static System.Math;using System;public class P{public long sum { get; set; }public string x { get; set; }}public class Hello{static void Main(){string[] line = Console.ReadLine().Trim().Split(' ');var n = int.Parse(line[0]);var w = long.Parse(line[1]);line = Console.ReadLine().Trim().Split(' ');var a = Array.ConvertAll(line, long.Parse);getAns(n, w, a);}static string change(string t){var res = "";foreach (var x in t){if (x == '2') res += "1";else res += x;}return res;}static long w0(int n, long[] a){var c = a.Count(x => x == 0);return (long)Pow(2, c) - 1L;}static void getAns(int n, long w, long[] a){if (w == 0) { Console.WriteLine(w0(n, a)); return; }var hs = new HashSet<string>();var q = new Queue<P>();q.Enqueue(new P { x = "2", sum = a[0] });q.Enqueue(new P { x = "1", sum = a[0] / 2L });q.Enqueue(new P { x = "0", sum = 0 });while (q.Count() > 0){var t = q.Dequeue();var tn = t.x.Length;if (tn == n){if (t.sum == w) hs.Add(change(t.x));continue;}if (t.sum + a[tn] <= w) q.Enqueue(new P { x = t.x + "2", sum = t.sum + a[tn] });if (t.sum + a[tn] / 2L <= w) q.Enqueue(new P { x = t.x + "1", sum = t.sum + a[tn] / 2L });q.Enqueue(new P { x = t.x + "0", sum = t.sum });}Console.WriteLine(hs.Count());}}