結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:09:09 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 7,310 bytes |
コンパイル時間 | 2,679 ms |
コンパイル使用メモリ | 78,512 KB |
実行使用メモリ | 84,872 KB |
最終ジャッジ日時 | 2024-10-15 02:57:34 |
合計ジャッジ時間 | 6,150 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
import java.io.*;import java.util.*;@SuppressWarnings("unused")public class Main {FastScanner in;PrintWriter out;final static int MOD = (int)1e9+7;final static long INF = Long.MAX_VALUE / 2;void solve(){int N = in.nextInt(), V = in.nextInt(), L = in.nextInt();int[] x = new int[N+1], v = new int[N+1], w = new int[N+1];for(int i = 1; i <= N; i++){x[i] = in.nextInt();v[i] = in.nextInt();w[i] = in.nextInt();}if(L - x[N] > V){out.println("-1");return;}long[][] dp = new long[N+1][V+1];for(int i = 0; i <= N; i++) for(int j = 0; j <= V; j++) dp[i][j] = INF;dp[0][V] = 0;for(int i = 0; i < N; i++){for(int j = 0; j <= V; j++){int m = j - (x[i+1] - x[i]);if(m < 0) continue;dp[i+1][m] = Math.min(dp[i+1][m], dp[i][j]);m = Math.min(m + v[i+1], V);dp[i+1][m] = Math.min(dp[i+1][m], dp[i][j] + w[i+1]);}}long ans = INF;for(int j = L - x[N]; j <= V; j++) ans = Math.min(ans, dp[N][j]);if(ans == INF) ans = -1;out.println(ans);}public static void main(String[] args) {new Main().m();}private void m() {in = new FastScanner(System.in);out = new PrintWriter(System.out);/*try {String path = "input.txt";out = new PrintWriter(new BufferedWriter(new FileWriter(new File(path))));}catch (IOException e){e.printStackTrace();}*/solve();out.flush();in.close();out.close();}static class FastScanner {private Reader input;public FastScanner() {this(System.in);}public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}public void close() {try {this.input.close();} catch (IOException e) {e.printStackTrace();}}public int nextInt() {return (int) nextLong();}public long nextLong() {try {int sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}long ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) return ret * sign;ret *= 10;ret += b - '0';}} catch (IOException e) {e.printStackTrace();return -1;}}public double nextDouble() {try {double sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}double ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) break;ret *= 10;ret += b - '0';}if (b != '.') return sign * ret;double div = 1;b = input.read();while ('0' <= b && b <= '9') {ret *= 10;ret += b - '0';div *= 10;b = input.read();}return sign * ret / div;} catch (IOException e) {e.printStackTrace();return Double.NaN;}}public char nextChar() {try {int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}return (char) b;} catch (IOException e) {e.printStackTrace();return 0;}}public String nextStr() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}while (b != -1 && !Character.isWhitespace(b)) {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public String nextLine() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (b != -1 && b != '\n') {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public int[] nextIntArray(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt();}return res;}public int[] nextIntArrayDec(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt() - 1;}return res;}public int[] nextIntArray1Index(int n) {int[] res = new int[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextInt();}return res;}public long[] nextLongArray(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong();}return res;}public long[] nextLongArrayDec(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong() - 1;}return res;}public long[] nextLongArray1Index(int n) {long[] res = new long[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextLong();}return res;}public double[] nextDoubleArray(int n) {double[] res = new double[n];for (int i = 0; i < n; i++) {res[i] = nextDouble();}return res;}}}