結果
| 問題 | No.1163 I want to be a high achiever |
| ユーザー |
 neko_the_shadow
|
| 提出日時 | 2020-08-31 12:43:45 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,419 bytes |
| コンパイル時間 | 3,093 ms |
| コンパイル使用メモリ | 97,544 KB |
| 実行使用メモリ | 653,740 KB |
| 最終ジャッジ日時 | 2024-04-27 16:30:01 |
| 合計ジャッジ時間 | 10,384 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 73 ms
51,156 KB |
| testcase_02 | AC | 78 ms
51,436 KB |
| testcase_03 | WA | - |
| testcase_04 | TLE | - |
| testcase_05 | MLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
package _1163;
import java.io.BufferedReader;
import java.io.EOFException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
public void exec() {
int n = stdin.nextInt();
long x = stdin.nextLong();
long[] a = stdin.nextLongArray(n);
long[] b = stdin.nextLongArray(n);
for (int i = 0; i < n; i++) {
a[i] -= x;
}
if (Arrays.stream(a).sum() >= 0) {
stdout.println(0);
return;
}
if (Arrays.stream(a).allMatch(v -> v < 0)) {
stdout.println(-1);
return;
}
List<Map<Long, Long>> dp = IntStream.range(0, n+1).mapToObj(unused -> new HashMap<Long, Long>()).collect(Collectors.toList());
// dp.get(0).put(0L, 0L);
for (int i = 0; i < n; i++) {
for (long k : dp.get(i).keySet()) {
dp.get(i+1).put(k, Math.min(dp.get(i+1).getOrDefault(k, Long.MAX_VALUE), dp.get(i).get(k)));
dp.get(i+1).put(k+a[i], Math.min(dp.get(i+1).getOrDefault(k+a[i], Long.MAX_VALUE), dp.get(i).get(k)+b[i]));
}
dp.get(i+1).put(a[i], Math.min(dp.get(i+1).getOrDefault(a[i], Long.MAX_VALUE), b[i]));
}
long ans = dp.get(n).entrySet().stream().filter(e -> e.getKey() >= 0).mapToLong(Entry::getValue).min().getAsLong();
stdout.println(ans);
}
private static final Stdin stdin = new Stdin();
private static final Stdout stdout = new Stdout();
public static void main(String[] args) {
try {
new Main().exec();
} finally {
stdout.flush();
}
}
public static class Stdin {
private BufferedReader stdin;
private Deque<String> tokens;
private Pattern delim;
public Stdin() {
stdin = new BufferedReader(new InputStreamReader(System.in));
tokens = new ArrayDeque<>();
delim = Pattern.compile(" ");
}
public String nextString() {
try {
if (tokens.isEmpty()) {
String line = stdin.readLine();
if (line == null) {
throw new UncheckedIOException(new EOFException());
}
delim.splitAsStream(line).forEach(tokens::addLast);
}
return tokens.pollFirst();
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
public int nextInt() {
return Integer.parseInt(nextString());
}
public double nextDouble() {
return Double.parseDouble(nextString());
}
public long nextLong() {
return Long.parseLong(nextString());
}
public String[] nextStringArray(int n) {
String[] a = new String[n];
for (int i = 0; i < n; i++) a[i] = nextString();
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 double[] nextDoubleArray(int n) {
double[] a = new double[n];
for (int i = 0; i < n; i++) a[i] = nextDouble();
return a;
}
public long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}
}
public static class Stdout {
private PrintWriter stdout;
public Stdout() {
stdout = new PrintWriter(System.out, false);
}
public void printf(String format, Object ... args) {
String line = String.format(format, args);
if (line.endsWith(System.lineSeparator())) {
stdout.print(line);
} else {
stdout.println(line);
}
}
public void println(Object ... objs) {
String line = Arrays.stream(objs).map(Objects::toString).collect(Collectors.joining(" "));
stdout.println(line);
}
public void debug(Object ... objs) {
String line = Arrays.stream(objs).map(this::deepToString).collect(Collectors.joining(" "));
stdout.printf("DEBUG: %s%n", line);
}
private String deepToString(Object o) {
if (o == null) {
return "null";
}
// 配列の場合
if (o.getClass().isArray()) {
int len = Array.getLength(o);
String[] tokens = new String[len];
for (int i = 0; i < len; i++) {
tokens[i] = deepToString(Array.get(o, i));
}
return "{" + String.join(",", tokens) + "}";
}
return Objects.toString(o);
}
private void flush() {
stdout.flush();
}
}
}