結果
問題 | No.2232 Miser's Gift |
ユーザー | 👑 kakel-san |
提出日時 | 2023-07-25 07:53:00 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 210 ms / 2,000 ms |
コード長 | 4,270 bytes |
コンパイル時間 | 2,734 ms |
コンパイル使用メモリ | 113,896 KB |
実行使用メモリ | 51,508 KB |
最終ジャッジ日時 | 2024-04-10 01:14:55 |
合計ジャッジ時間 | 11,005 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
25,496 KB |
testcase_01 | AC | 32 ms
25,264 KB |
testcase_02 | AC | 34 ms
27,416 KB |
testcase_03 | AC | 197 ms
47,372 KB |
testcase_04 | AC | 143 ms
49,032 KB |
testcase_05 | AC | 49 ms
33,116 KB |
testcase_06 | AC | 33 ms
27,136 KB |
testcase_07 | AC | 61 ms
33,364 KB |
testcase_08 | AC | 209 ms
47,424 KB |
testcase_09 | AC | 204 ms
47,292 KB |
testcase_10 | AC | 206 ms
47,416 KB |
testcase_11 | AC | 207 ms
47,540 KB |
testcase_12 | AC | 209 ms
49,580 KB |
testcase_13 | AC | 198 ms
46,844 KB |
testcase_14 | AC | 200 ms
47,232 KB |
testcase_15 | AC | 200 ms
45,180 KB |
testcase_16 | AC | 200 ms
47,236 KB |
testcase_17 | AC | 204 ms
47,096 KB |
testcase_18 | AC | 202 ms
47,104 KB |
testcase_19 | AC | 203 ms
47,096 KB |
testcase_20 | AC | 203 ms
48,896 KB |
testcase_21 | AC | 202 ms
46,976 KB |
testcase_22 | AC | 201 ms
49,160 KB |
testcase_23 | AC | 210 ms
49,596 KB |
testcase_24 | AC | 207 ms
49,596 KB |
testcase_25 | AC | 209 ms
49,456 KB |
testcase_26 | AC | 210 ms
51,508 KB |
testcase_27 | AC | 208 ms
49,580 KB |
testcase_28 | AC | 187 ms
49,148 KB |
testcase_29 | AC | 190 ms
49,272 KB |
testcase_30 | AC | 190 ms
49,292 KB |
testcase_31 | AC | 194 ms
49,416 KB |
testcase_32 | AC | 193 ms
49,292 KB |
testcase_33 | AC | 204 ms
47,100 KB |
testcase_34 | AC | 204 ms
49,292 KB |
testcase_35 | AC | 207 ms
49,144 KB |
testcase_36 | AC | 204 ms
45,196 KB |
testcase_37 | AC | 204 ms
49,028 KB |
testcase_38 | AC | 33 ms
25,644 KB |
testcase_39 | AC | 34 ms
25,460 KB |
testcase_40 | AC | 33 ms
25,632 KB |
testcase_41 | AC | 34 ms
25,504 KB |
testcase_42 | AC | 34 ms
27,612 KB |
testcase_43 | AC | 34 ms
27,628 KB |
testcase_44 | AC | 34 ms
25,376 KB |
testcase_45 | AC | 34 ms
25,628 KB |
testcase_46 | AC | 34 ms
23,476 KB |
testcase_47 | AC | 34 ms
25,588 KB |
testcase_48 | AC | 33 ms
25,264 KB |
testcase_49 | AC | 32 ms
25,224 KB |
testcase_50 | AC | 32 ms
25,628 KB |
testcase_51 | AC | 33 ms
27,528 KB |
testcase_52 | AC | 32 ms
25,216 KB |
testcase_53 | AC | 32 ms
27,272 KB |
testcase_54 | AC | 32 ms
25,368 KB |
testcase_55 | AC | 32 ms
27,388 KB |
testcase_56 | AC | 33 ms
27,640 KB |
testcase_57 | AC | 33 ms
27,516 KB |
コンパイルメッセージ
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 int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); // Test(); } static void Test() { var r = new Random(); var count = 0; while (true) { var n = 2; var t = r.Next(1, 20); var map = new int[n][]; for (var i = 0; i < n; ++i) map[i] = new int[] { r.Next(1, 10), r.Next(1, 10) }; // 愚直解 var s1 = All(n, t, map); // 作成解 var s2 = Gift(n, t, map); if (s1 != s2) { WriteLine(n + " " + t); WriteLine(string.Join("\n", map.Select(m => string.Join(" ", m)))); WriteLine(s1); WriteLine(s2); return; } ++count; if (count % 1000 == 0) WriteLine(count); } } static string All(int n, int w, int[][] map) { var ans = new int[w]; for (var x = 1; x <= w; ++x) { for (var v = 1; v <= 100; ++v) { var dp = Enumerable.Repeat(long.MinValue, w + 1).ToArray(); var valid = new bool[w + 1]; dp[0] = 0; dp[x] = v; valid[x] = true; for (var i = 0; i < n; ++i) { var ndp = (long[]) dp.Clone(); var nv = (bool[]) valid.Clone(); for (var j = 0; j < w; ++j) { if (j + map[i][0] >= ndp.Length) break; if (ndp[j + map[i][0]] <= dp[j] + map[i][1]) { ndp[j + map[i][0]] = dp[j] + map[i][1]; nv[j + map[i][0]] = valid[j]; } } dp = ndp; valid = nv; // if (x == 4 && v == 1) // { // WriteLine(string.Join(" ", dp)); // WriteLine(string.Join(" ", valid.Select(f => f ? "Y" : "N"))); // } } for (var i = 1; i < dp.Length; ++i) dp[i] = Math.Max(dp[i], dp[i - 1]); var max = dp[w]; var flg = false; for (var i = 0; i < dp.Length; ++i) { if (dp[i] == max) { flg = valid[i]; break; } } // if (x == 4 && v == 1) WriteLine(flg); if (flg) { ans[x - 1] = v; break; } } } return string.Join(" ", ans); } static void Solve() { var c = NList; var (n, w) = (c[0], c[1]); var map = NArr(n); // WriteLine(All(n, w, map)); WriteLine(Gift(n, w, map)); } static string Gift(int n, int w, int[][] map) { var INF = long.MinValue; var init = Enumerable.Repeat(INF, w + 1).ToArray(); var dp = (long[]) init.Clone(); dp[0] = 0; for (var i = 0; i < n; ++i) { var ndp = (long[]) dp.Clone(); for (var j = 0; j < dp.Length; ++j) { if (j + map[i][0] >= ndp.Length) break; ndp[j + map[i][0]] = Math.Max(ndp[j + map[i][0]], dp[j] + map[i][1]); } dp = ndp; // WriteLine(string.Join(" ", dp)); } for (var i = 1; i < dp.Length; ++i) dp[i] = Math.Max(dp[i], dp[i - 1]); var ans = new long[w]; for (var i = 0; i < ans.Length; ++i) ans[i] = dp[w] - dp[w - i - 1] + 1; return string.Join("\n", ans); } }