結果
問題 |
No.1083 余りの余り
|
ユーザー |
![]() |
提出日時 | 2020-12-04 11:48:34 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 163 ms / 3,000 ms |
コード長 | 1,425 bytes |
コンパイル時間 | 2,577 ms |
コンパイル使用メモリ | 79,160 KB |
実行使用メモリ | 43,372 KB |
最終ジャッジ日時 | 2024-09-14 22:05:16 |
合計ジャッジ時間 | 8,325 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
import java.util.*; public class Main { static int n; static int[] values; static HashMap<Integer, HashMap<Integer, Integer>> dp = new HashMap<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); int k = sc.nextInt(); values = new int[n]; for (int i = 0; i < n; i++) { values[i] = sc.nextInt(); } System.out.println(dfw((1 << n) - 1, k)); } static int dfw(int key, int value) { if (key == 0) { return value; } if (dp.containsKey(key)) { if (dp.get(key).containsKey(value)) { return dp.get(key).get(value); } } else { dp.put(key, new HashMap<>()); } int tmp = key; for (int i = 0; i < n; i++) { if ((tmp & (1 << i)) == 0) { continue; } if (values[i] > value) { tmp ^= (1 << i); } } if (tmp == 0) { dp.get(key).put(value, value); return value; } int max = 0; for (int i = 0; i < n; i++) { if ((tmp & (1 << i)) == 0) { continue; } max = Math.max(max, dfw(tmp ^ (1 << i), value % values[i])); } dp.get(key).put(value, max); return max; } }