結果

問題 No.286 Modulo Discount Store
ユーザー ぴろず
提出日時 2015-10-09 22:27:10
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 172 ms
コード長 705 Byte
コンパイル時間 1,481 ms
使用メモリ 25,236 KB
最終ジャッジ日時 2018-12-05 20:10:41

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 113 ms
24,340 KB
case2.txt AC 113 ms
22,896 KB
case3.txt AC 123 ms
22,712 KB
case4.txt AC 155 ms
24,416 KB
case5.txt AC 120 ms
25,040 KB
case6.txt AC 109 ms
24,960 KB
case7.txt AC 146 ms
24,412 KB
case8.txt AC 109 ms
24,700 KB
case9.txt AC 108 ms
25,012 KB
case10.txt AC 108 ms
24,184 KB
case11.txt AC 119 ms
22,724 KB
case12.txt AC 111 ms
24,184 KB
case13.txt AC 108 ms
25,016 KB
case14.txt AC 119 ms
24,892 KB
case15.txt AC 109 ms
25,040 KB
case16.txt AC 109 ms
24,500 KB
case17.txt AC 110 ms
24,184 KB
case18.txt AC 124 ms
24,392 KB
case19.txt AC 115 ms
24,404 KB
case20.txt AC 133 ms
24,220 KB
case21.txt AC 124 ms
24,716 KB
case22.txt AC 130 ms
23,272 KB
case23.txt AC 122 ms
22,496 KB
case24.txt AC 145 ms
25,236 KB
case25.txt AC 128 ms
24,416 KB
case26.txt AC 154 ms
24,480 KB
case27.txt AC 111 ms
22,488 KB
case28.txt AC 114 ms
24,196 KB
case29.txt AC 125 ms
24,924 KB
case30.txt AC 112 ms
24,192 KB
case31.txt AC 113 ms
24,660 KB
case32.txt AC 114 ms
24,196 KB
case33.txt AC 112 ms
24,216 KB
case34.txt AC 111 ms
24,164 KB
case35.txt AC 172 ms
24,364 KB
case36.txt AC 124 ms
22,496 KB
case37.txt AC 111 ms
24,192 KB
case38.txt AC 113 ms
24,484 KB
case39.txt AC 109 ms
24,216 KB
case40.txt AC 123 ms
24,392 KB
sample1.txt AC 110 ms
24,992 KB
sample2.txt AC 108 ms
25,044 KB
sample3.txt AC 106 ms
24,332 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