結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-08-04 10:23:43 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,404 bytes |
コンパイル時間 | 3,622 ms |
コンパイル使用メモリ | 78,604 KB |
実行使用メモリ | 52,320 KB |
最終ジャッジ日時 | 2024-09-16 15:01:12 |
合計ジャッジ時間 | 14,262 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 WA * 24 |
ソースコード
import java.io.*;import java.util.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int m = sc.nextInt();int p = sc.nextInt();int max = 0;TreeMap<Integer, Integer> map = new TreeMap<>();for (int i = 0; i < n; i++) {int x = sc.nextInt();max = Math.max(max, x);int count = 0;while (x % p == 0) {x /= p;count++;}map.put(count, Math.max(map.getOrDefault(count, 0), x));}boolean all1 = true;for (int x : map.values()) {if (x > 1) {all1 = false;break;}}if (all1) {System.out.println(-1);return;}int limit = (m + max - 1) / max;int ans = Integer.MAX_VALUE;Integer current = 0;TreeMap<Integer, Integer> dp = new TreeMap<>();dp.put(1, 0);while ((current = dp.higherKey(current)) != null) {for (Map.Entry<Integer, Integer> entry : map.entrySet()) {int count = entry.getKey() + 1;int value = entry.getValue();if (value == 1) {continue;}if (current * (long)value >= limit) {ans = Math.min(ans, dp.get(current) + count);} else {if (!dp.containsKey(current * value) || dp.get(current * value) > dp.get(current) + count) {dp.put(current * value, dp.get(current) + count);}}}}System.out.println(ans + 1);}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public String next() throws Exception {if (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}