結果
問題 | No.472 平均順位 |
ユーザー |
![]() |
提出日時 | 2017-07-05 19:22:17 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 963 ms / 2,000 ms |
コード長 | 1,247 bytes |
コンパイル時間 | 2,427 ms |
コンパイル使用メモリ | 77,324 KB |
実行使用メモリ | 48,124 KB |
最終ジャッジ日時 | 2024-10-05 20:02:06 |
合計ジャッジ時間 | 10,396 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int P = sc.nextInt();int[] a = new int[N];int[] b = new int[N];int[] c = new int[N];for(int i = 0; i < N; i++) {a[i] = sc.nextInt();b[i] = sc.nextInt();c[i] = sc.nextInt();}// dp[j]はコンテストiまでで正解数がちょうどj問の場合の順位の和の最小値(有り得ない場合は0とする)int[] dp = new int[P + 1];dp[0] = a[0];if(1 < P + 1) dp[1] = b[0];if(2 < P + 1) dp[2] = c[0];if(3 < P + 1) dp[3] = 1;int[] arr = dp.clone();for(int i = 1; i < N; i++) {for(int j = 0; j < P + 1; j++) {int min = Integer.MAX_VALUE;if(arr[j] != 0) min = Math.min(min, a[i] + arr[j]);if(j >= 1 && arr[j - 1] != 0) min = Math.min(min, b[i] + arr[j - 1]);if(j >= 2 && arr[j - 2] != 0) min = Math.min(min, c[i] + arr[j - 2]);if(j >= 3 && arr[j - 3] != 0) min = Math.min(min, 1 + arr[j - 3]);if(min == Integer.MAX_VALUE) min = 0;dp[j] = min;}arr = dp.clone();}System.out.println((double)dp[P] / (double)N);}}