fork download 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.util.stream.*;
  4.  
  5. /**
  6.     Nathan
  7. */
  8. public class Main {
  9.     public static void solve(FastScanner io) throws Exception {
  10.         int n = io.nextInt(), k = io.nextInt();
  11.  
  12.         int[] c = new int[n];
  13.         for (int i = 0; i < n; i++) c[i] = io.nextInt();
  14.  
  15.         List<String>[] dp = new ArrayList[k+1];
  16.         for (int i = 0; i <= k; i++) dp[i] = new ArrayList<>();
  17.         dp[0].add("");
  18.  
  19.         for (int i = 0; i < n; i++) {
  20.             for (int j = k; j >= c[i]; j--) {
  21.                 List<String> prev = dp[j-c[i]];
  22.                 for (String p : prev) {
  23.                     StringBuilder sb = new StringBuilder(p);
  24.                     sb.append("#").append(c[i]);
  25.                     dp[j].add(sb.toString());
  26.                 }
  27.             }
  28.         }
  29.  
  30.         Set<Integer> unique = new HashSet<>();
  31.         unique.add(0);
  32.  
  33.         List<String> subsets = dp[k];
  34.         for (String subset : subsets) {
  35.             boolean[] pos = new boolean[k+1];
  36.             pos[0] = true;
  37.  
  38.             String[] s = subset.split("#");
  39.             int[] xs = new int[s.length-1];
  40.             for (int i = 1; i < s.length; i++) {
  41.                 xs[i-1] = Integer.parseInt(s[i]);
  42.             }
  43.  
  44.             for (int x : xs) {
  45.                 for (int j = k; j >= x; j--) {
  46.                     if (pos[j]) continue;
  47.                     pos[j] |= pos[j-x];
  48.                     if (pos[j]) unique.add(j);
  49.                 }
  50.             }
  51.         }
  52.  
  53.         io.println(unique.size());
  54.         for (int i = 0; i <= k; i++) {
  55.             if (unique.contains(i)) io.print(i + " ");
  56.         }
  57.     }
  58.  
  59.     /**
  60.         MAIN
  61.     */
  62.     public static void main(String[] args) throws Exception {
  63.         // FastScanner io = new FastScanner("usaco-problem-name"); // usaco
  64.         FastScanner io = new FastScanner();
  65. 		int t = 1;
  66.         // t = io.nextInt(); // t testcases
  67. 		while (t-->0) {
  68.             solve(io);
  69.         }
  70.         io.close();
  71.     }
  72.  
  73.     /**
  74.         RESERVED INSTANCES
  75.     */
  76.     static int mod_fermat = 998_244_353;
  77.     static int mod_prime = 1_000_000_007; // prime number
  78.     static int oo_int = (int)1e9; // infinity number (int)
  79. 	static long oo_long = (long) 2e18; // infinity number
  80. 	static Random random = new Random();
  81.     // mod trick: modular inverse of 2 under 1e9+7
  82.     // 1e9+7 is prime -> inv(2) = (1e9+7+1)/2
  83.     static int inv2 = 500_000_004;
  84.  
  85. 	/**
  86. 		HELPER
  87. 	*/
  88.  
  89.     // ALGEBRA
  90. 	static long add(long a, long b) { return (a + b) % mod_prime; }
  91. 	static long subtract(long a, long b) { return ((a - b) % mod_prime + mod_prime) % mod_prime; }
  92. 	static long multiply(long a, long b) { return (a * b) % mod_prime; }
  93. 	static long exp(long base, long exp) { 
  94. 		long result = 1;
  95. 		while (exp > 0) {
  96. 			if ((exp & 1) == 1) result = multiply(result, base);
  97. 			base = multiply(base, base);
  98. 			exp >>=1;
  99. 		}
  100. 		return result;
  101. 	}
  102.     static long abs(long x) { return Math.abs(x); }
  103.     static int abs(int x) { return Math.abs(x); }
  104.     static int sign(long x) { return x < 0 ? -1 : 1; }
  105.  
  106.     // NUMBER THEORY
  107.     static int gcd(int a, int b) { 
  108.         while (b > 0) {
  109.             int r = a % b;
  110.             a = b;
  111.             b = r;
  112.         }
  113.         return a;
  114.     }
  115.     static int lcm(int a, int b) { return a * b / gcd(a,b); }
  116.     static int binpow(int a, int b) {
  117.         int res = 1;
  118.         while (b > 0) {
  119.             if (b % 2 != 0)
  120.                 res = res * a;
  121.             a = a * a;
  122.             b >>= 1;
  123.         }
  124.         return res;
  125.     }
  126.     static boolean[] sieve(int n) {
  127.         boolean[] prime = new boolean[n+1];
  128.         Arrays.fill(prime, true);
  129.         prime[0] = prime[1] = false;
  130.         for (int i = 2; i * i <= n; i++) {
  131.             if (prime[i]) {
  132.                 for (int j = i * i; j <= n; j += i)
  133.                     prime[j] = false;
  134.             }
  135.         }
  136.         return prime;
  137.     }
  138.     static int[] primeFactorization(int n) {
  139.         int[] prime = new int[n+1];
  140.         for (int p = 2; p * p <= n; p++) {
  141.             while (n % p == 0) {
  142.                 prime[p]++;
  143.                 n /= p;
  144.             }
  145.         }
  146.         if (n > 1) prime[n] = 1; // if n is a large prime
  147.         return prime;
  148.     }
  149.  
  150.     // ARRAY OPERATIONS
  151.     static void swap(int a, int b) { int temp = a; a = b; b = temp; }
  152.     static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
  153.     static void shuffle(int[] a) { 
  154.         int n = a.length;
  155.         for (int i = 0; i < n; i++) {
  156.             int ri = random.nextInt(n); // random index
  157.             swap(a, i, ri);
  158.         }
  159.     }
  160.     static <T> void reverse(List<T> x) { Collections.reverse(x); }
  161.     static int max(int[] a) { Arrays.sort(a); return a[a.length-1]; }
  162.     static long max(long[] a) { Arrays.sort(a); return a[a.length-1]; }
  163.  
  164.     // HASHING
  165.     static String hash(int[] x) { return Arrays.toString(x); }
  166.     static String hash(long[] x) { return Arrays.toString(x); }
  167.     static <T> String hash(List<T> x) { return x.toString(); }
  168.  
  169.     // SORTING
  170.     static void sort(int[] a) { Arrays.sort(a); }
  171.     static void sort(long[] a) { Arrays.sort(a); }
  172.     static <T extends Comparable<? super T>> void sort(List<T> a) { Collections.sort(a); }
  173.     static void ruffleSort(int[] a) { shuffle(a); sort(a); }
  174.  
  175.     // FACTORIALS & nCk
  176. 	static long[] factorials = new long[2_000_005];
  177. 	static long[] inverseFactorials = new long[2_000_005];
  178. 	static void precomputeFactorials() {
  179.         int n = factorials.length;
  180. 		factorials[0] = 1;
  181. 		for (int i = 1; i < factorials.length; i++) {
  182. 			factorials[i] = multiply(factorials[i-1], i);
  183. 		}
  184.         inverseFactorials[n-1] = exp(factorials[n-1], mod_prime-2);
  185.         for (int i = n-2; i >= 0; i--) {
  186.             inverseFactorials[i] = multiply(inverseFactorials[i+1], i);
  187.         }
  188. 	}
  189.     static long nCk(int n, int k) {
  190.         if (n < 0 || k < 0 || n < k) return 0;
  191.         return multiply(factorials[n], multiply(inverseFactorials[n-k], inverseFactorials[k]));
  192.     }
  193.  
  194.     // STRING
  195.     static String repeat(String s, int count) { return s.repeat(count); }
  196.  
  197.     // BINARY SEARCH
  198.     static int[] binarySearch(int x, int[] a) {
  199.         // looking for transition point
  200.         int l = -1, r = a.length-1;
  201.         while (r - l > 1) {
  202.             int mid = (l + r) >>> 1;
  203.             if (x < a[mid]) r = mid;
  204.             else l = mid;
  205.         }
  206.         // l = last element >= x (-1 if no such element) -- lowerbound
  207.         // r = first element > x (n if no such element) -- upperbound
  208.         // a[l] <= x < a[r]
  209.         return new int[]{l,r};
  210.     }
  211.  
  212.     /**
  213.         DATA STRUCTURES TEMPLATES
  214.     */
  215.     static abstract class Multiset<T> {
  216.         protected final TreeMap<T, Integer> multiset;
  217. 		public Multiset() { multiset = new TreeMap<>(); }
  218.         public void add(T x) { multiset.merge(x, 1, Integer::sum); }
  219.         public void remove(T x) {
  220.             multiset.merge(x, -1, Integer::sum); 
  221.             if (multiset.get(x) <= 0) multiset.remove(x);
  222.         }
  223.         public T min() { return multiset.firstKey(); }
  224.         public T max() { return multiset.lastKey(); }
  225.         public int countLE(T x) { // count less than or equal
  226.             return multiset.headMap(x, true).values()
  227.                     .stream().mapToInt(Integer::intValue).sum();
  228.         }
  229.         public int count() { return multiset.values().stream().mapToInt(Integer::intValue).sum(); }
  230.     }
  231.  
  232.     static abstract class DSU {
  233.         protected final int[] parent;
  234.         protected final int[] size;
  235.         public DSU(int n) {
  236.             parent = new int[n];
  237.             size = new int[n];
  238.             for (int i = 0; i < n; i++) {
  239.                 parent[i] = i;
  240.                 size[i] = 1;
  241.             }
  242.         }
  243.         public int find(int v) {
  244.             return parent[v] == v ? v : (parent[v] = find(parent[v]));
  245.         }
  246.         public boolean union(int a, int b) {
  247.             a = find(a);
  248.             b = find(b);
  249.             if (a == b) return false;
  250.             if (size[a] < size[b]) swap(a, b);
  251.             parent[b] = a;
  252.             size[a] += size[b];
  253.             return true;
  254.         }
  255.         public int size(int v) {
  256.             return size[find(v)];
  257.         }
  258.         public boolean connected(int a, int b) {
  259.             return find(a) == find(b);
  260.         }
  261.     }
  262.  
  263.     static abstract class SegmentTree { 
  264.         protected final int[] st;
  265.         protected final int[] lazy;
  266.         protected final int[] a;
  267.         public SegmentTree(int n, int[] a) {
  268.             this.st = new int[4*n];
  269.             this.lazy = new int[4*n];
  270.             this.a = a;
  271.         }
  272.         protected abstract int combine(int left, int right);
  273.         public void build(int v, int tl, int tr) {
  274.             if (tl == tr) {
  275.                 st[v] = a[tl];
  276.                 return;
  277.             }
  278.             int tm = (tl + tr) >>> 1;
  279.             build(v*2+1, tl, tm);
  280.             build(v*2+2, tm+1, tr);
  281.             st[v] = combine(st[v*2+1], st[v*2+2]);
  282.         }
  283.         protected abstract int update(int x, int u);
  284.         protected abstract int updateLazy(int x, int u);
  285.         protected abstract void push(int v); // lazy propagation
  286.         public void update(int v, int tl, int tr, int pos, int u) {
  287.             if (tl > tr) return;
  288.             if (tl == tr) {
  289.                 st[v] = update(st[v], u);
  290.                 lazy[v] = updateLazy(lazy[v], u);
  291.                 return;
  292.             }
  293.             int tm = (tl + tr) >>> 1;
  294.             if (pos <= tm) update(v*2+1, tl, tm, pos, u);
  295.             else update(v*2+2, tm+1, tr, pos, u);
  296.             st[v] = combine(st[v*2+1], st[v*2+2]);
  297.         }
  298.         protected abstract int identity();
  299.         public int query(int v, int tl, int tr, int l, int r) {
  300.             if (l > r) return identity();
  301.             if (l <= tl && tr <= r) return st[v];
  302.             push(v);
  303.             int tm = (tl + tr) >>> 1;
  304.             int left = query(v*2+1, tl, tm, l, Math.min(r, tm));
  305.             int right = query(v*2+2, tm+1, tr, Math.max(l, tm+1), r);
  306.             return combine(left, right);
  307.         }
  308.     }
  309.  
  310.     static abstract class FenwickTree {
  311.         /**
  312.         supporting
  313.             1. point update
  314.             2. range sum query (prefix sum)
  315.         note: one-indexed (zero is skipped)
  316.  
  317.         ft[k] = sum(k - p(k) + 1, k)
  318.         p(k) = largest power of 2 that divides k
  319.  
  320.         use least significant one (lsone) to update/calc sum
  321.             * lsone(k) = k & (-k)
  322.             * defined in CP2 (Steven & Helix)
  323.  
  324.         sum(a,b) = sum(1,b) - sum(1,a-1) for a > 1
  325.  
  326.         it is obvious there is no easy way to find minimum in range [l,r] for fenwick tree
  327.             * FT can only answer min [0,r], update(s) would make it a disaster
  328.             * MATH explanation :) 
  329.                 - because min() together with the set of integers doesn't form a group, 
  330.                 as there are no inverse elements.
  331.             * "Efficient Range Minimum Queries using Binary Indexed Trees" does provide min for BIT,
  332.                 but complex to be implemented in CP setting
  333.  
  334.         extra theoretical read: TopCoder Binary Indexed Trees
  335.         */
  336.         int[] ft; // fenwick tree
  337.         int[] a; // original array
  338.         public FenwickTree(int n) {
  339.             ft = new int[n+1];
  340.             a = new int[n+1];
  341.         }
  342.         void set(int k, int u) {
  343.             add(k, u - a[k]);
  344.         }
  345.         void add(int k, int u) {
  346.             a[k] += u;
  347.             for (; k <= ft.length; k += lsone(k)) ft[k] += u;
  348.         }
  349.         void rangeAdd(int l, int r, int u) {
  350.             // difference-array (or "prefix‑difference") trick
  351.             add(l, u);
  352.             add(r+1, -u);
  353.         }
  354.         int sum(int k) {
  355.             int s = 0;
  356.             for (; k > 0; k -= lsone(k)) s += ft[k];
  357.             return s;
  358.         }
  359.         int lsone(int x) { // least significant one
  360.             return x & (-x);
  361.         }
  362.     }
  363.  
  364.     static abstract class FenwickTree2D {
  365.         int[][] ft;
  366.         int[][] a;
  367.         int n, m;
  368.         public FenwickTree2D(int n, int m) {
  369.             ft = new int[n+1][m+1];
  370.             a = new int[n+1][m+1];
  371.             this.n = n; this.m = m;
  372.         }
  373.         void set(int x, int y, int u) {
  374.             add(x, y, u - a[x][y]);
  375.         }
  376.         void add(int x, int y, int u) {
  377.             // note: avoid update x and y in-place
  378.             //       by setting i = x and j = y
  379.             a[x][y] += u;
  380.             for (int i = x; i <= n; i += lsone(i)) {
  381.                 for (int j = y; j <= m; j += lsone(j)) {
  382.                     ft[i][j] += u;
  383.                 }
  384.             }
  385.         }
  386.         int sum(int x, int y) {
  387.             int s = 0;
  388.             for (int i = 0; i > 0; i -= lsone(i)) {
  389.                 for (int j = 0; j > 0; j -= lsone(j)) {
  390.                     s += ft[i][j];
  391.                 }
  392.             }
  393.             return s;
  394.         }
  395.         int rectangleSum(int x1, int y1, int x2, int y2) {
  396.             int s = 0;
  397.             s += sum(x2, y2);
  398.             s -= sum(x2, y1-1);
  399.             s -= sum(x1-1, y2);
  400.             s += sum(x1-1, y1-1);
  401.             return s;
  402.         }
  403.         int lsone(int k) {
  404.             return k & (-k);
  405.         }
  406.     }
  407.  
  408.     /**
  409.         PRINTING 
  410.     */
  411.     static void print(FastScanner io, int[] a, String delimeter) { io.println(Arrays.stream(a).mapToObj(String::valueOf).collect(Collectors.joining(delimeter))); }
  412.     static void print(FastScanner io, long[] a, String delimeter) { io.println(Arrays.stream(a).mapToObj(String::valueOf).collect(Collectors.joining(delimeter))); }
  413.     static void print(FastScanner io, List<?> a, String delimeter) { io.println(a.stream().map(String::valueOf).collect(Collectors.joining(delimeter))); }
  414.  
  415.     /**
  416.         IO
  417.     */
  418.     static class FastScanner extends PrintWriter {
  419.         private BufferedReader br;
  420.         private StringTokenizer st;
  421. 		// standard input
  422.         public FastScanner() { this(System.in, System.out); }
  423. 		public FastScanner(InputStream i, OutputStream o) {
  424.             super(o);
  425. 			st = new StringTokenizer("");
  426.             br = new BufferedReader(new InputStreamReader(i));
  427.         }
  428. 		// USACO-style file input
  429.         public FastScanner(String problemName) throws IOException {
  430.             super(problemName + ".out");
  431. 			st = new StringTokenizer("");
  432.             br = new BufferedReader(new FileReader(problemName + ".in"));
  433.         }
  434.         // returns null if no more input
  435.         public String next() {
  436.             try {
  437.                 while (st == null || !st.hasMoreTokens())
  438.                     st = new StringTokenizer(br.readLine());
  439.                 return st.nextToken();
  440.             } catch (Exception e) { }
  441.             return null;
  442.         }
  443.         public String nextLine() {
  444.             try {
  445.                 return br.readLine();
  446.             } catch (IOException e) {
  447.                 return null;
  448.             }
  449.         }
  450.         public int nextInt() { return Integer.parseInt(next()); }  
  451.         public double nextDouble() { return Double.parseDouble(next()); }   
  452.         public long nextLong() { return Long.parseLong(next()); }   
  453.         public int[] nextArray(int n) { int[] a = new int[n]; return nextArray(a); }
  454.         public int[] nextArray(int[] a) { for (int i = 0; i < a.length; i++) a[i] = nextInt(); return a; }
  455.         public long[] nextArray(long[] a) { for (int i = 0; i < a.length; i++) a[i] = nextLong(); return a; }
  456.     }
  457. }
  458.  
Success #stdin #stdout 0.16s 86624KB
comments (?)
stdin 
6 18
5 6 1 10 12 2
stdout 
16
0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18
https://ideone.com/UjtA3E
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!