結果

問題 No.286 Modulo Discount Store
ユーザー しらっ亭
提出日時 2015-10-09 22:41:18
言語 Java8
(openjdk 1.8.0.181)
結果
AC  
実行時間 112 ms
コード長 5,801 Byte
コンパイル時間 1,701 ms
使用メモリ 24,568 KB
最終ジャッジ日時 2018-09-23 03:16:21

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 76 ms
22,680 KB
case2.txt AC 81 ms
22,132 KB
case3.txt AC 102 ms
22,960 KB
case4.txt AC 78 ms
23,668 KB
case5.txt AC 78 ms
23,092 KB
case6.txt AC 78 ms
22,956 KB
case7.txt AC 110 ms
23,608 KB
case8.txt AC 76 ms
22,680 KB
case9.txt AC 78 ms
24,296 KB
case10.txt AC 79 ms
22,416 KB
case11.txt AC 90 ms
21,132 KB
case12.txt AC 78 ms
23,276 KB
case13.txt AC 76 ms
22,684 KB
case14.txt AC 101 ms
24,532 KB
case15.txt AC 76 ms
24,292 KB
case16.txt AC 79 ms
23,900 KB
case17.txt AC 79 ms
21,520 KB
case18.txt AC 112 ms
22,976 KB
case19.txt AC 89 ms
22,692 KB
case20.txt AC 77 ms
20,784 KB
case21.txt AC 81 ms
23,372 KB
case22.txt AC 79 ms
23,780 KB
case23.txt AC 80 ms
21,772 KB
case24.txt AC 104 ms
24,124 KB
case25.txt AC 76 ms
24,292 KB
case26.txt AC 81 ms
22,684 KB
case27.txt AC 76 ms
24,296 KB
case28.txt AC 83 ms
21,520 KB
case29.txt AC 112 ms
23,624 KB
case30.txt AC 75 ms
22,684 KB
case31.txt AC 76 ms
22,888 KB
case32.txt AC 77 ms
22,684 KB
case33.txt AC 80 ms
24,272 KB
case34.txt AC 79 ms
24,000 KB
case35.txt AC 77 ms
22,692 KB
case36.txt AC 78 ms
23,896 KB
case37.txt AC 75 ms
22,712 KB
case38.txt AC 82 ms
22,748 KB
case39.txt AC 79 ms
24,180 KB
case40.txt AC 111 ms
24,568 KB
sample1.txt AC 77 ms
24,288 KB
sample2.txt AC 78 ms
22,888 KB
sample3.txt AC 77 ms
21,772 KB
テストケース一括ダウンロード

ソースコード

diff #
package problems285;

import java.io.BufferedReader;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.Arrays;

public class Main {

    public void run() throws IOException {
        int N = io.nextInt();
        int[] M = io.nextIntArray(N);

        int[] sum = new int[1 << N];
        int[] wari = new int[1 << N];
        for (int i = 0; i < 1 << N; i++) {
            for (int j = 0; j < N; j++) {
                int j1 = 1 << j;
                if ((i & j1) == 0) {
                    sum[i + j1] = sum[i] + M[j];
                    wari[i + j1] = sum[i + j1] % 1000;
                }
            }
        }

        int[] dp = new int[1 << N];

        for (int i = 0; i < 1 << N; i++) {
            for (int j = 0; j < N; j++) {
                int j1 = 1 << j;
                if ((i & j1) == 0) {
                    dp[i + j1] = Integer.max(dp[i + j1], dp[i] + Integer.min(M[j], wari[i]));
                }
            }
        }

        System.out.println(sum[(1 << N) - 1] - dp[(1 << N) - 1]);

    }

    // @formatter:off
    private static final int mod = (int) 1e9 + 7;
    final IOFast io = new IOFast();

    void main() throws IOException { try { run(); } catch (RuntimeException ignore) { } finally { io.out.flush(); } }
    public static void main(String[] args) throws IOException { new Main().main(); }

    public static String dtos(double x, int n) {
        StringBuilder sb = new StringBuilder();
        if (x < 0) {
            sb.append('-');
            x = -x;
        }
        x += Math.pow(10, -n) / 2;
        sb.append((long) x);
        sb.append(".");
        x -= (long) x;
        for (int i = 0; i < n; i++) {
            x *= 10;
            sb.append((int) x);
            x -= (int) x;
        }
        return sb.toString();
    }

    public static class IOFast {
        private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        private PrintWriter out = new PrintWriter(System.out);

        void setStringIn(String input) throws IOException { in.close(); in = new BufferedReader(new StringReader(input)); }
        void setStringOut(ByteArrayOutputStream output) throws IOException { System.out.flush(); System.setOut(new PrintStream(output)); }
        void setStringIO(String input, ByteArrayOutputStream output) throws IOException { setStringIn(input); setStringOut(output); }

        private static int pos, readLen;
        private static final char[] buffer = new char[1024 * 8];
        private static char[] str = new char[500*8*2];
        private static boolean[] isDigit = new boolean[256];
        private static boolean[] isSpace = new boolean[256];
        private static boolean[] isLineSep = new boolean[256];

        static { for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; }
        public int read() throws IOException { if(pos >= readLen) { pos = 0; readLen = in.read(buffer); if(readLen <= 0) { throw new RuntimeException(); } } return buffer[pos++]; }
        public int nextInt() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
        public long nextLong() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
        public char nextChar() throws IOException { while(true) { final int c = read(); if(!isSpace[c]) { return (char)c; } } }
        int reads(int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } if(str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char)c; } } catch(RuntimeException e) { ; } return len; }
        public char[] nextLine() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isLineSep); try { if(str[len-1] == '\r') { len--; read(); } } catch(RuntimeException e) { ; } return Arrays.copyOf(str, len); }
        public String nextString() throws IOException { return new String(next()); }
        public char[] next() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); return Arrays.copyOf(str, len); }
        public double nextDouble() throws IOException { return Double.parseDouble(nextString()); }
        public long[] nextLongArray(final int n) throws IOException { final long[] res = new long[n]; for(int i = 0; i < n; i++) { res[i] = nextLong(); } return res; }
        public int[] nextIntArray(final int n) throws IOException { final int[] res = new int[n]; for(int i = 0; i < n; i++) { res[i] = nextInt(); } return res; }
        public int[][] nextIntArray2D(final int n, final int k) throws IOException { final int[][] res = new int[n][]; for(int i = 0; i < n; i++) { res[i] = nextIntArray(k); } return res; }
        public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException { final int[][] res = new int[n][k+1]; for(int i = 0; i < n; i++) { for(int j = 0; j < k; j++) { res[i][j] = nextInt(); } res[i][k] = i; } return res; }
        public double[] nextDoubleArray(final int n) throws IOException { final double[] res = new double[n]; for(int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; }
    }
    // @formatter:on
}
0