結果
問題 | No.1861 Required Number |
ユーザー |
|
提出日時 | 2022-03-04 23:11:24 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,500 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 940 ms |
コンパイル使用メモリ | 113,372 KB |
実行使用メモリ | 53,448 KB |
最終ジャッジ日時 | 2024-07-18 23:15:49 |
合計ジャッジ時間 | 10,807 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 MLE * 4 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static void Main() { var c = NList; var (n, k) = (c[0], c[1]); var a = NList; Array.Sort(a); var dp1 = new bool[n + 1][]; for (var i = 0; i < dp1.Length; ++i) dp1[i] = new bool[k + 1]; dp1[0][0] = true; for (var i = 0; i < n; ++i) { dp1[i + 1][0] = true; for (var j = 0; j <= k; ++j) { if (dp1[i][j]) { dp1[i + 1][j] = true; if (j + a[i] <= k) dp1[i + 1][j + a[i]] = true; } } } if (!dp1[n][k]) { WriteLine(-1); return; } var dp2 = new bool[n + 1][]; for (var i = 0; i < dp2.Length; ++i) dp2[i] = new bool[k + 1]; dp2[n][0] = true; for (var i = n - 1; i >= 0; --i) { for (var j = 0; j <= k; ++j) { if (dp2[i + 1][j]) { dp2[i][j] = true; if (j + a[i] <= k) dp2[i][j + a[i]] = true; } } } var res = 0; for (var i = 0; i < n; ++i) { var flg = false; for (var j = 0; j <= k; ++j) { if (dp1[i][j] && dp2[i + 1][k - j]) { flg = true; break; } } if (!flg) ++res; } WriteLine(res); } }