Language: Java


import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H

??¨??§???????????¶????????????
????????? vi ????????? wi ??§??????????????? N ??????????????¨???????????? W ??????????????¶?????????????????????????¬?????????¶?????????????????????????????????????????§???????????¶???????????\????????????

???????????????????????????????¨??????§???????????????????????????
???????????????????????????????????? W ????¶?????????????
?????????????¨?????????§???????±??????????????????????

??\???
???????????????????????´??°???N???W???????????????????????§?????????????????????????????? ?¶???? N ?????§ i ???????????????????????? vi ??¨?????? wi ????????????????????§?????????????????????

??????
?????????????¨?????????§??????????????????????????????????????????

??¶?´?
1 ??? N ??? 40
1 ??? vi ??? 10^15
1 ??? wi ??? 10^15
1 ??? W ??? 10^15
??\?????????

??\?????? 1
4 5
4 2
5 2
2 1
8 3
????????? 1
13

??\?????? 2
2 20
5 9
4 10
????????? 2
9

 ?????????????????????
 1. ?????????????????????????????????????????????(v,w)
 2. for each pair (v1[i],w1[i]) in group one, we find max(v1[i] + v2[j]), for every j such that w2[j] <= W - w1[i]
 3. Sort (v2, w2) by w2. then we have
 3.1 w2[i] <= w2[j] for each i < j
 3.2 then we filter out all i such that w2[i] <= w2[j] and v2[i] < v2[j]
*/
public class Main {
    public static class Solver {
        long solve(final long W, List<Long> values, List<Long> weights) {
            int N = values.size();
            int n1 = N >> 1;

            List<Pair> gp1 = getCombinations(0, n1).stream().map((comb) ->
                    comb.stream()
                        .map((i) -> new Pair(values.get(i), weights.get(i)))
                        .reduce((p1, p2) -> new Pair(p1.value + p2.value, p1.weight + p2.weight))
                        .get()
            ).collect(Collectors.toList());

            List<Pair> gp2 = getCombinations(n1, N).stream().map((comb) ->
                    comb.stream()
                            .map((i) -> new Pair(values.get(i), weights.get(i)))
                            .reduce((p1, p2) -> new Pair(p1.value + p2.value, p1.weight + p2.weight))
                            .get()
            ).collect(Collectors.toList());

            Collections.sort(gp2, Comparator.comparingLong(p -> p.weight));

//            System.out.println(gp1);
//            System.out.println(gp2);

            List<Pair> filteredGp2 = new ArrayList<>();
            Pair prev = null;
            for (int i = 0; i < gp2.size(); ++i) {
                if (null == prev || prev.value < gp2.get(i).value) {
                    prev = gp2.get(i);
                    filteredGp2.add(prev);
                }
            }


            long ret = 0;
            for (Pair p : gp1) {
                long w = W - p.weight;
                int idx = Collections.binarySearch(filteredGp2, new Pair(-1, w), Comparator.comparingLong(pp -> pp.weight));
                long v = 0;
                if (idx < 0) {
                    idx = -idx - 1;
                    if (idx > 0) {
                        idx = filteredGp2.size() == idx ? filteredGp2.size() - 1 : idx;
                        v = filteredGp2.get(idx).value;
                    }
                }
                ret = Math.max(ret, v + p.value);
            }
            return ret;
        }

        private static List<List<Integer>> getCombinations(int idx, int length) {
            List<Integer> comb = new ArrayList<>();
            List<List<Integer>> combs = new ArrayList<>();
            getCombinations(idx, length, comb, combs);
            return combs;
        }

        private static void getCombinations(int idx, int length, List<Integer> comb, List<List<Integer>> combs) {
            if (idx == length) {
                if (comb.size() != 0) {
                    combs.add(new ArrayList<>(comb));
                }
                return;
            }
            {
                comb.add(idx);
                getCombinations(idx + 1, length, comb, combs);
                comb.remove(comb.size() - 1);
            }
            {
                getCombinations(idx + 1, length, comb, combs);
            }
        }

        private static class Pair {
            private final long value;
            private final long weight;
            private Pair(long value, long weight) {
                this.value = value;
                this.weight = weight;
            }

            @Override
            public String toString() {
                return String.format("[v:%d,w:%d]", value, weight);
            }
        }
    }

    private static final Pattern SPLIT = Pattern.compile("\\s");
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Long> weights = new ArrayList<>();
        List<Long> values = new ArrayList<>();
        List<Long> NW = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
                .collect(Collectors.toList());
        final long N = NW.get(0);
        final long W = NW.get(1);
        for (int i = 0; i < N; ++i) {
            List<Long> collect = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
                    .collect(Collectors.toList());
            values.add(collect.get(0));
            weights.add(collect.get(1));
        }
        System.out.println(new Solver().solve(W, values, weights));
    }
}

Compiler output:
Main.java:53: error: cannot find symbol
        long solve(final long W, List<Long> values, List<Long> weights) {
                                 ^
  symbol:   class List
  location: class Solver
Main.java:53: error: cannot find symbol
        long solve(final long W, List<Long> values, List<Long> weights) {
                                                    ^
  symbol:   class List
  location: class Solver
Main.java:103: error: cannot find symbol
        private static List<List<Integer>> getCombinations(int idx, int length) {
                       ^
  symbol:   class List
  location: class Solver
Main.java:103: error: cannot find symbol
        private static List<List<Integer>> getCombinations(int idx, int length) {
                            ^
  symbol:   class List
  location: class Solver
Main.java:110: error: cannot find symbol
        private static void getCombinations(int idx, int length, List<Integer> comb, List<List<Integer>> combs) {
                                                                 ^
  symbol:   class List
  location: class Solver
Main.java:110: error: cannot find symbol
        private static void getCombinations(int idx, int length, List<Integer> comb, List<List<Integer>> combs) {
                                                                                     ^
  symbol:   class List
  location: class Solver
Main.java:110: error: cannot find symbol
        private static void getCombinations(int idx, int length, List<Integer> comb, List<List<Integer>> combs) {
                                                                                          ^
  symbol:   class List
  location: class Solver
Main.java:57: error: cannot find symbol
            List<Pair> gp1 = getCombinations(0, n1).stream().map((comb) ->
            ^
  symbol:   class List
  location: class Solver
Main.java:64: error: cannot find symbol
            List<Pair> gp2 = getCombinations(n1, N).stream().map((comb) ->
            ^
  symbol:   class List
  location: class Solver
Main.java:71: error: cannot find symbol
            Collections.sort(gp2, Comparator.comparingLong(p -> p.weight));
            ^
  symbol:   variable Collections
  location: class Solver
Main.java:71: error: cannot find symbol
            Collections.sort(gp2, Comparator.comparingLong(p -> p.weight));
                                  ^
  symbol:   variable Comparator
  location: class Solver
Main.java:76: error: cannot find symbol
            List<Pair> filteredGp2 = new ArrayList<>();
            ^
  symbol:   class List
  location: class Solver
Main.java:76: error: cannot find symbol
            List<Pair> filteredGp2 = new ArrayList<>();
                                         ^
  symbol:   class ArrayList
  location: class Solver
Main.java:89: error: cannot find symbol
                int idx = Collections.binarySearch(filteredGp2, new Pair(-1, w), Comparator.comparingLong(pp -> pp.weight));
                          ^
  symbol:   variable Collections
  location: class Solver
Main.java:89: error: cannot find symbol
                int idx = Collections.binarySearch(filteredGp2, new Pair(-1, w), Comparator.comparingLong(pp -> pp.weight));
                                                                                 ^
  symbol:   variable Comparator
  location: class Solver
Main.java:104: error: cannot find symbol
            List<Integer> comb = new ArrayList<>();
            ^
  symbol:   class List
  location: class Solver
Main.java:104: error: cannot find symbol
            List<Integer> comb = new ArrayList<>();
                                     ^
  symbol:   class ArrayList
  location: class Solver
Main.java:105: error: cannot find symbol
            List<List<Integer>> combs = new ArrayList<>();
            ^
  symbol:   class List
  location: class Solver
Main.java:105: error: cannot find symbol
            List<List<Integer>> combs = new ArrayList<>();
                 ^
  symbol:   class List
  location: class Solver
Main.java:105: error: cannot find symbol
            List<List<Integer>> combs = new ArrayList<>();
                                            ^
  symbol:   class ArrayList
  location: class Solver
Main.java:113: error: cannot find symbol
                    combs.add(new ArrayList<>(comb));
                                  ^
  symbol:   class ArrayList
  location: class Solver
Main.java:144: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:144: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
Main.java:145: error: cannot find symbol
        List<Long> weights = new ArrayList<>();
        ^
  symbol:   class List
  location: class Main
Main.java:145: error: cannot find symbol
        List<Long> weights = new ArrayList<>();
                                 ^
  symbol:   class ArrayList
  location: class Main
Main.java:146: error: cannot find symbol
        List<Long> values = new ArrayList<>();
        ^
  symbol:   class List
  location: class Main
Main.java:146: error: cannot find symbol
        List<Long> values = new ArrayList<>();
                                ^
  symbol:   class ArrayList
  location: class Main
Main.java:147: error: cannot find symbol
        List<Long> NW = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
        ^
  symbol:   class List
  location: class Main
Main.java:152: error: cannot find symbol
            List<Long> collect = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
            ^
  symbol:   class List
  location: class Main
29 errors