結果
| 問題 | No.417 チューリップバブル |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-08-14 00:45:24 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,057 ms / 2,000 ms |
| コード長 | 4,692 bytes |
| コンパイル時間 | 4,106 ms |
| コンパイル使用メモリ | 81,564 KB |
| 実行使用メモリ | 57,992 KB |
| 最終ジャッジ日時 | 2024-11-07 17:48:18 |
| 合計ジャッジ時間 | 22,121 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 40 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;public class チューリップバブル {static InputStream is;static PrintWriter out;static String INPUT = "";class Pair {long u;int t;Pair(long u, int t) {this.u = u;this.t = t;}}void solver() {int n = ni();// 村の数int m = ni();// 残り時間long[] u = new long[n];for (int i = 0; i < n; i++) {u[i] = nl();// 税収}ArrayList<Edge>[] e = new ArrayList[n];for (int i = 0; i < n; i++) {e[i] = new ArrayList<>();}for (int i = 0; i < n - 1; i++) {int a = ni();int b = ni();int c = ni();e[a].add(new Edge(c, a, b));e[b].add(new Edge(c, b, a));}long[] list = dfs(-1, 0, e, u, m);long ans = 0;for (int i = 0; i <= m; i++) {ans = Math.max(ans, list[i]);}out.println(ans);}long[] dfs(int p, int cur, ArrayList<Edge>[] e, long[] u, int m) {if (m < 0) {return new long[0];}long[] now = new long[m + 1];Arrays.fill(now, -1);now[0] = u[cur];for (int i = 0; i < e[cur].size(); i++) {Edge v = e[cur].get(i);if (v.to != p) {long[] d = dfs(cur, v.to, e, u, m - 2 * v.time);long[] next = Arrays.copyOf(now, now.length);for (int j = 0; j <= m; j++) {for (int k = 0; k <= m; k++) {if (2 * v.time + j + k <= m && d[j] != -1 && now[k] != -1) {if (next[2 * v.time + j + k] < d[j] + now[k]) {next[2 * v.time + j + k] = d[j] + now[k];}}}}now = next;}}return now;}static class Edge {int time;int from;int to;Edge(int time, int from, int to) {this.time = time;this.from = from;this.to = to;}}class State {long u;int t;State(long u, int t) {this.u = u;this.t = t;}}public static void main(String[] args) throws Exception {is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long t = System.currentTimeMillis();new チューリップバブル().solver();System.err.println(System.currentTimeMillis() - t);out.flush();}static void tr(Object... o) {System.out.println(Arrays.deepToString(o));}static long nl() {try {long num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}static char nc() {try {int b = skip();if (b == -1)return 0;return (char) b;} catch (IOException e) {}return 0;}static double nd() {try {return Double.parseDouble(ns());} catch (Exception e) {}return 0;}static String ns() {try {int b = skip();StringBuilder sb = new StringBuilder();if (b == -1)return "";sb.append((char) b);while (true) {b = is.read();if (b == -1)return sb.toString();if (b <= ' ')return sb.toString();sb.append((char) b);}} catch (IOException e) {}return "";}public static char[] ns(int n) {char[] buf = new char[n];try {int b = skip(), p = 0;if (b == -1)return null;buf[p++] = (char) b;while (p < n) {b = is.read();if (b == -1 || b <= ' ')break;buf[p++] = (char) b;}return Arrays.copyOf(buf, p);} catch (IOException e) {}return null;}public static byte[] nse(int n) {byte[] buf = new byte[n];try {int b = skip();if (b == -1)return null;is.read(buf);return buf;} catch (IOException e) {}return null;}static int skip() throws IOException {int b;while ((b = is.read()) != -1 && !(b >= 33 && b <= 126));return b;}static boolean eof() {try {is.mark(1000);int b = skip();is.reset();return b == -1;} catch (IOException e) {return true;}}static int ni() {try {int num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}}