結果

問題 No.286 Modulo Discount Store
ユーザー ぴろず
提出日時 2015-10-09 22:27:10
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 141 ms
コード長 705 Byte
コンパイル時間 1,530 ms
使用メモリ 21,540 KB
最終ジャッジ日時 2019-05-14 23:38:29

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 87 ms
21,152 KB
case2.txt AC 86 ms
21,144 KB
case3.txt AC 101 ms
21,432 KB
case4.txt AC 111 ms
21,152 KB
case5.txt AC 105 ms
21,172 KB
case6.txt AC 109 ms
21,156 KB
case7.txt AC 129 ms
21,480 KB
case8.txt AC 132 ms
21,380 KB
case9.txt AC 129 ms
21,212 KB
case10.txt AC 132 ms
21,220 KB
case11.txt AC 137 ms
21,420 KB
case12.txt AC 131 ms
21,220 KB
case13.txt AC 130 ms
21,188 KB
case14.txt AC 136 ms
21,436 KB
case15.txt AC 129 ms
21,152 KB
case16.txt AC 130 ms
21,216 KB
case17.txt AC 131 ms
21,216 KB
case18.txt AC 141 ms
21,540 KB
case19.txt AC 138 ms
21,420 KB
case20.txt AC 130 ms
21,180 KB
case21.txt AC 130 ms
21,220 KB
case22.txt AC 131 ms
21,212 KB
case23.txt AC 130 ms
21,220 KB
case24.txt AC 135 ms
21,440 KB
case25.txt AC 132 ms
21,216 KB
case26.txt AC 134 ms
21,228 KB
case27.txt AC 131 ms
21,208 KB
case28.txt AC 133 ms
21,224 KB
case29.txt AC 141 ms
21,508 KB
case30.txt AC 131 ms
21,216 KB
case31.txt AC 130 ms
21,216 KB
case32.txt AC 132 ms
21,200 KB
case33.txt AC 132 ms
21,224 KB
case34.txt AC 129 ms
21,212 KB
case35.txt AC 129 ms
21,212 KB
case36.txt AC 130 ms
21,220 KB
case37.txt AC 130 ms
21,216 KB
case38.txt AC 134 ms
21,196 KB
case39.txt AC 133 ms
21,416 KB
case40.txt AC 138 ms
21,476 KB
sample1.txt AC 132 ms
21,184 KB
sample2.txt AC 130 ms
21,224 KB
sample3.txt AC 130 ms
21,216 KB
テストケース一括ダウンロード

ソースコード

diff #
package no286;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		int[] dp = new int[1<<n];
		Arrays.fill(dp, 1<<29);
		dp[0] = 0;
		for(int i=0;i<1<<n;i++) {
			int discount = 0;
			for(int j=0;j<n;j++) {
				if ((i >> j & 1) == 1) {
					discount += a[j];
				}
			}
			discount %= 1000;
			for(int j=0;j<n;j++) {
				if ((i >> j & 1) == 0) {
					int to = i|(1<<j);
					dp[to] = Math.min(dp[to], dp[i] + Math.max(a[j] - discount , 0));
				}
			}
		}
		System.out.println(dp[(1<<n)-1]);

	}

}
0