結果
問題 |
No.1111 コード進行
|
ユーザー |
![]() |
提出日時 | 2020-07-10 22:49:56 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 672 ms / 2,000 ms |
コード長 | 3,137 bytes |
コンパイル時間 | 4,409 ms |
コンパイル使用メモリ | 79,488 KB |
実行使用メモリ | 265,244 KB |
最終ジャッジ日時 | 2024-10-11 10:09:29 |
合計ジャッジ時間 | 12,165 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
import java.util.*; import java.io.*; public class Main { static int n,m,k; static ArrayList<Music> li; public static void main(String[] args) throws Exception { FastScanner sc = new FastScanner(System.in); long mod = (long)Math.pow(10,9)+7; n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt(); li = new ArrayList<>(); for(int i = 0; i < m; i++){ int p = sc.nextInt()-1; int q = sc.nextInt()-1; int c = sc.nextInt(); li.add(new Music(p,q,c)); } Collections.sort(li); long[][][] dp = new long[300][n+1][k+2]; for(int i = 0; i < 300; i++){ dp[i][1][0] = 1; } for(int i = 2; i <= n; i++){ for(Music m : li){ for(int j = k-m.c; j >= 0; j--){ dp[m.q][i][j+m.c] += dp[m.p][i-1][j]; dp[m.q][i][j+m.c] %= mod; } } } long ans = 0; for(int i = 0; i < 300; i++){ ans += dp[i][n][k]; ans %= mod; } System.out.println(ans); } } class Music implements Comparable<Music>{ int p,q,c; public Music(int p, int q, int c){ this.p = p; this.q = q; this.c = c; } public int compareTo(Music m){ if(this.c > m.c){ return -1; }else if(this.c < m.c){ return 1; }else{ return 0; } } } class FastScanner { private BufferedReader reader = null; private StringTokenizer tokenizer = null; public FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } public String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } public double nextDouble() { return Double.parseDouble(next()); } public String[] nextArray(int n) { String[] a = new String[n]; for (int i = 0; i < n; i++) a[i] = next(); return a; } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } }