結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2021-05-03 10:40:21 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,497 ms / 2,000 ms |
コード長 | 2,020 bytes |
コンパイル時間 | 1,108 ms |
コンパイル使用メモリ | 115,536 KB |
実行使用メモリ | 75,484 KB |
最終ジャッジ日時 | 2024-07-21 23:25:59 |
合計ジャッジ時間 | 11,121 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
コンパイルメッセージ
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 System; public class P { public int q { get; set; } public int c { get; set; } } public class Hello { public static int n, m, k; public static int MOD = 1000000007; static void Main() { string[] line = Console.ReadLine().Trim().Split(' '); n = int.Parse(line[0]); m = int.Parse(line[1]); k = int.Parse(line[2]); var ps = new List<P>[301]; for (int i = 0; i < 301; i++) ps[i] = new List<P>(); var hs = new HashSet<int>(); for (int i = 0; i < m; i++) { line = Console.ReadLine().Trim().Split(' '); var p = int.Parse(line[0]); var q = int.Parse(line[1]); var c = int.Parse(line[2]); if (c <= k) { ps[p].Add(new P { q = q, c = c }); hs.Add(p); } } var plist = hs.ToArray(); Array.Sort(plist); getAns(ps, plist); } static void getAns(List<P>[] ps, int[] plist) { var dp = new int[n, 301, k + 1]; foreach (var x in plist) foreach (var y in ps[x]) { dp[1, y.q, y.c]++; dp[1, y.q, y.c] %= MOD; } for (int i = 0; i < n - 1; i++) { for (int j = 1; j <= 300; j++) { for (int L = 0; L <= k; L++) { foreach (var x in ps[j]) { var ww = L + x.c; if (ww <= k) { dp[i + 1, x.q, ww] += dp[i, j, L]; dp[i + 1, x.q, ww] %= MOD; } } } } } var ans = 0L; for (int i = 1; i <= 300; i++) { ans += dp[n - 1, i, k]; ans %= MOD; } Console.WriteLine(ans); } }