Submission #2559019
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n ; i++) { a[i] = in.nextInt(); } int sum = 0; for (int i = 0; i < n ; i++) { sum += a[i]; } int half = (sum + 1) / 2; BitVector bit = BitVector.canMake(a); for (int i = half ; i <= sum ; i++) { if (bit.get(i)) { out.println(i); break; } } out.flush(); } public static class BitVector { public int n; public int m; public long[] bits; public BitVector(int length) { n = length; bits = new long[(n+63)>>>6]; m = bits.length; } public void set(int at) { bits[at>>>6] |= 1L<<(at&63); } public void set(int at, boolean s) { if (s) { bits[at>>>6] |= 1L<<(at&63); } else { bits[at>>>6] &= ~(1L<<(at&63)); } } public boolean get(int at) { int big = at >>> 6 ; if (big >= bits.length) { return false; } return ((bits[big] >>> (at&63)) & 1) == 1; } public BitVector shiftLeft(int l) { BitVector ret = new BitVector(n+l); int big = l >>> 6; int small = l & 63; for (int i = 0; i < m ; i++) { ret.bits[i+big] |= bits[i] << small; } if (small >= 1) { for (int i = 0; i+big+1 < ret.m; i++) { ret.bits[i+big+1] |= (bits[i] >>> (64-small)); } } return ret; } public BitVector or(BitVector o) { BitVector ans = new BitVector(Math.max(n, o.n)); for (int i = 0; i < ans.m ; i++) { if (i < m) { ans.bits[i] = bits[i]; } if (i < o.m) { ans.bits[i] |= o.bits[i]; } } return ans; } public static BitVector canMake(int[] x) { Map<Integer,Integer> cnt = new HashMap<>(); for (int i = 0; i < x.length ; i++) { cnt.put(x[i], cnt.getOrDefault(x[i],0)+1); } List<Integer> t = new ArrayList<>(); for (int k : cnt.keySet()) { int v = cnt.get(k); int l = 1; while (l <= v) { v -= l; t.add(k * l); l *= 2; } if (v >= 1) { t.add(k * v); } } Collections.sort(t); BitVector v = new BitVector(1); v.set(0); for (int ti : t) { v = v.or(v.shiftLeft(ti)); } return v; } } public static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private 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 char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); 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 double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | C - Median Sum |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 5803 Byte |
Status | AC |
Exec Time | 249 ms |
Memory | 139092 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 70 ms | 19412 KB |
sample_02.txt | AC | 71 ms | 18900 KB |
subtask_1_01.txt | AC | 71 ms | 21460 KB |
subtask_1_02.txt | AC | 69 ms | 19540 KB |
subtask_1_03.txt | AC | 72 ms | 20948 KB |
subtask_1_04.txt | AC | 77 ms | 21332 KB |
subtask_1_05.txt | AC | 99 ms | 22996 KB |
subtask_1_06.txt | AC | 85 ms | 21588 KB |
subtask_1_07.txt | AC | 249 ms | 106324 KB |
subtask_1_08.txt | AC | 239 ms | 139092 KB |
subtask_1_09.txt | AC | 219 ms | 84936 KB |
subtask_1_10.txt | AC | 95 ms | 23892 KB |
subtask_1_11.txt | AC | 100 ms | 23892 KB |
subtask_1_12.txt | AC | 103 ms | 25936 KB |
subtask_1_13.txt | AC | 104 ms | 21332 KB |
subtask_1_14.txt | AC | 103 ms | 26196 KB |
subtask_1_15.txt | AC | 103 ms | 24916 KB |
subtask_1_16.txt | AC | 108 ms | 27604 KB |
subtask_1_17.txt | AC | 123 ms | 35668 KB |
subtask_1_18.txt | AC | 130 ms | 40660 KB |
subtask_1_19.txt | AC | 142 ms | 39624 KB |
subtask_1_20.txt | AC | 151 ms | 58068 KB |
subtask_1_21.txt | AC | 100 ms | 22356 KB |
subtask_1_22.txt | AC | 104 ms | 27476 KB |
subtask_1_23.txt | AC | 105 ms | 28116 KB |
subtask_1_24.txt | AC | 110 ms | 28500 KB |
subtask_1_25.txt | AC | 68 ms | 19412 KB |
subtask_1_26.txt | AC | 71 ms | 18388 KB |
subtask_1_27.txt | AC | 70 ms | 19284 KB |
subtask_1_28.txt | AC | 71 ms | 19412 KB |
subtask_1_29.txt | AC | 69 ms | 17620 KB |
subtask_1_30.txt | AC | 69 ms | 21460 KB |
subtask_1_31.txt | AC | 71 ms | 18772 KB |
subtask_1_32.txt | AC | 69 ms | 19412 KB |
subtask_1_33.txt | AC | 75 ms | 20436 KB |
subtask_1_34.txt | AC | 89 ms | 17748 KB |
subtask_1_35.txt | AC | 81 ms | 22740 KB |
subtask_1_36.txt | AC | 98 ms | 23764 KB |
subtask_1_37.txt | AC | 76 ms | 18388 KB |
subtask_1_38.txt | AC | 95 ms | 21716 KB |