Submission #242885


Source Code Expand

Copy
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

/**
 * Created by hama_du on 2014/09/27.
 */
public class Main {
    static int[][] graph;
    static long[][] sum;
    static long[] a;

    static void dfs(int now, int parent) {
        sum[now][0] = 0;
        sum[now][1] = Math.min(sum[now][1], a[now]);

        int sl = sum[now].length;

        for (int to : graph[now]) {
            if (to == parent) {
                continue;
            }

            dfs(to, now);

            long[] part = sum[to];
            for (int t = sl-1 ; t >= 2 ; t--) {
                for (int p = 1 ; p < sl ; p++) {
                    if (sum[now][p] == Long.MAX_VALUE) {
                        break;
                    }
                    int pp = t - p;
                    if (pp <= 0) {
                        break;
                    }
                    if (part[pp] < Long.MAX_VALUE) {
                        sum[now][t] = Math.min(sum[now][t], sum[now][p] + part[pp]);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }

        graph = buildGraph(in, n, n-1);
        sum = new long[n][n+1];
        for (int i = 0 ; i < n ; i++) {
            Arrays.fill(sum[i], Long.MAX_VALUE);
        }

        int m = in.nextInt();
        long[] r = new long[m];
        for (int i = 0 ; i < m ; i++) {
            r[i] = in.nextLong();
        }
        Arrays.sort(r);

        dfs(0, -1);

        long all = 0;
        for (int i = 0 ; i < a.length ; i++) {
            all += a[i];
        }

        long max = all;
        long get = 0;
        long lose = 0;
        for (int u = 1 ; u <= Math.min(a.length, r.length) ; u++) {
            get += r[r.length-u];
            lose = sum[0][u];
            long p = all + get - lose;
            max = Math.max(max, p);
        }

        out.println(max);
        out.flush();
    }
    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }


    static int[][] buildGraph(InputReader in, int n, int m) {
        int[][] edges = new int[m][];
        int[][] graph = new int[n][];
        int[] deg = new int[n];
        for (int i = 0 ; i < m ; i++) {
            int a = in.nextInt()-1;
            int b = in.nextInt()-1;
            deg[a]++;
            deg[b]++;
            edges[i] = new int[]{a, b};
        }
        for (int i = 0 ; i < n ; i++) {
            graph[i] = new int[deg[i]];
        }
        for (int i = 0 ; i < m ; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            graph[a][--deg[a]] = b;
            graph[b][--deg[b]] = a;
        }
        return graph;
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

Submission Info

Submission Time
Task D - 高橋君と木のおもちゃ
User hamadu
Language Java (OpenJDK 1.7.0)
Score 30
Code Size 5491 Byte
Status TLE
Exec Time 2085 ms
Memory 267332 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 10 / 10 20 / 20 0 / 70
Status
AC × 2
AC × 32
AC × 62
AC × 68
TLE × 24
Set Name Test Cases
Sample subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt AC 380 ms 20744 KB
subtask0-sample-02.txt AC 370 ms 20724 KB
subtask1-01.txt AC 377 ms 20804 KB
subtask1-02.txt AC 375 ms 20728 KB
subtask1-03.txt AC 373 ms 20768 KB
subtask1-04.txt AC 377 ms 20728 KB
subtask1-05.txt AC 380 ms 20832 KB
subtask1-06.txt AC 378 ms 20752 KB
subtask1-07.txt AC 382 ms 20844 KB
subtask1-08.txt AC 371 ms 20856 KB
subtask1-09.txt AC 368 ms 20792 KB
subtask1-10.txt AC 377 ms 20804 KB
subtask1-11.txt AC 374 ms 20816 KB
subtask1-12.txt AC 422 ms 20752 KB
subtask1-13.txt AC 406 ms 20768 KB
subtask1-14.txt AC 407 ms 20696 KB
subtask1-15.txt AC 387 ms 20696 KB
subtask1-16.txt AC 390 ms 20772 KB
subtask1-17.txt AC 396 ms 20724 KB
subtask1-18.txt AC 372 ms 20764 KB
subtask1-19.txt AC 378 ms 20724 KB
subtask1-20.txt AC 400 ms 20804 KB
subtask1-21.txt AC 410 ms 20784 KB
subtask1-22.txt AC 408 ms 20760 KB
subtask1-23.txt AC 397 ms 20792 KB
subtask1-24.txt AC 394 ms 20736 KB
subtask1-25.txt AC 394 ms 20724 KB
subtask1-26.txt AC 378 ms 20760 KB
subtask1-27.txt AC 379 ms 20692 KB
subtask1-28.txt AC 390 ms 20796 KB
subtask1-29.txt AC 384 ms 20764 KB
subtask1-30.txt AC 384 ms 20768 KB
subtask2-01.txt AC 402 ms 20764 KB
subtask2-02.txt AC 374 ms 20804 KB
subtask2-03.txt AC 390 ms 20764 KB
subtask2-04.txt AC 370 ms 20656 KB
subtask2-05.txt AC 370 ms 20804 KB
subtask2-06.txt AC 366 ms 20752 KB
subtask2-07.txt AC 373 ms 20768 KB
subtask2-08.txt AC 376 ms 20804 KB
subtask2-09.txt AC 384 ms 20788 KB
subtask2-10.txt AC 377 ms 20856 KB
subtask2-11.txt AC 364 ms 20728 KB
subtask2-12.txt AC 378 ms 20772 KB
subtask2-13.txt AC 369 ms 20764 KB
subtask2-14.txt AC 372 ms 20864 KB
subtask2-15.txt AC 387 ms 20788 KB
subtask2-16.txt AC 373 ms 20760 KB
subtask2-17.txt AC 377 ms 20660 KB
subtask2-18.txt AC 379 ms 20764 KB
subtask2-19.txt AC 382 ms 20828 KB
subtask2-20.txt AC 389 ms 20652 KB
subtask2-21.txt AC 373 ms 20708 KB
subtask2-22.txt AC 373 ms 20764 KB
subtask2-23.txt AC 379 ms 20796 KB
subtask2-24.txt AC 376 ms 20704 KB
subtask2-25.txt AC 379 ms 20772 KB
subtask2-26.txt AC 373 ms 20736 KB
subtask2-27.txt AC 383 ms 20728 KB
subtask2-28.txt AC 410 ms 21944 KB
subtask2-29.txt AC 410 ms 22236 KB
subtask2-30.txt AC 423 ms 22700 KB
subtask3-01.txt AC 420 ms 23376 KB
subtask3-02.txt AC 479 ms 27224 KB
subtask3-03.txt AC 561 ms 36576 KB
subtask3-04.txt AC 548 ms 36240 KB
subtask3-05.txt AC 917 ms 57804 KB
subtask3-06.txt AC 1600 ms 96424 KB
subtask3-07.txt TLE 2053 ms 168636 KB
subtask3-08.txt TLE 2065 ms 264284 KB
subtask3-09.txt TLE 2064 ms 263836 KB
subtask3-10.txt TLE 2069 ms 266472 KB
subtask3-11.txt TLE 2063 ms 266204 KB
subtask3-12.txt TLE 2062 ms 266900 KB
subtask3-13.txt TLE 2069 ms 266532 KB
subtask3-14.txt TLE 2085 ms 266904 KB
subtask3-15.txt TLE 2066 ms 266372 KB
subtask3-16.txt TLE 2071 ms 267044 KB
subtask3-17.txt TLE 2067 ms 266836 KB
subtask3-18.txt TLE 2068 ms 266800 KB
subtask3-19.txt TLE 2067 ms 266528 KB
subtask3-20.txt TLE 2065 ms 266476 KB
subtask3-21.txt TLE 2063 ms 267332 KB
subtask3-22.txt TLE 2065 ms 266784 KB
subtask3-23.txt TLE 2065 ms 266820 KB
subtask3-24.txt TLE 2067 ms 266764 KB
subtask3-25.txt TLE 2066 ms 266828 KB
subtask3-26.txt TLE 2063 ms 266492 KB
subtask3-27.txt TLE 2063 ms 266724 KB
subtask3-28.txt TLE 2069 ms 266380 KB
subtask3-29.txt TLE 2066 ms 266620 KB
subtask3-30.txt TLE 2067 ms 266768 KB