結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2020-08-18 07:28:43 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 558 ms / 2,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 2,281 ms |
コンパイル使用メモリ | 79,516 KB |
実行使用メモリ | 171,468 KB |
最終ジャッジ日時 | 2024-10-11 20:21:26 |
合計ジャッジ時間 | 15,142 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
import java.util.*; public class Main { static ArrayList<HashMap<Integer, Integer>> list = new ArrayList<>(); static int[][][] dp; static final int MOD = 1000000007; public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); for (int i = 0; i <= 300; i++) { list.add(new HashMap<>()); } for (int i = 0; i < m; i++) { int p = sc.nextInt(); int q = sc.nextInt(); int c = sc.nextInt(); list.get(q).put(p, c); } dp = new int[n][k + 1][301]; for (int[][] arr1 : dp) { for (int[] arr2 : arr1) { Arrays.fill(arr2, -1); } } int ans = 0; for (int i = 1; i <= 300; i++) { ans += dfw(n - 1, k, i); ans %= MOD; } System.out.println(ans); } static int dfw(int idx, int value, int code) { if (idx == 0 && value == 0) { return 1; } if (idx <= 0 || value < 0) { return 0; } if (dp[idx][value][code] >= 0) { return dp[idx][value][code]; } int ans = 0; for (Map.Entry<Integer, Integer> entry : list.get(code).entrySet()) { ans += dfw(idx - 1, value - entry.getValue(), entry.getKey()); ans %= MOD; } dp[idx][value][code] = ans; return ans; } }