結果

問題 No.37 遊園地のアトラクション
ユーザー scache
提出日時 2014-10-09 23:53:13
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 177 ms
コード長 749 Byte
コンパイル時間 1,536 ms
使用メモリ 21,524 KB
最終ジャッジ日時 2019-10-15 18:42:42

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 126 ms
21,476 KB
input1.txt AC 128 ms
21,460 KB
input2.txt AC 127 ms
21,468 KB
input3.txt AC 126 ms
21,460 KB
input4.txt AC 127 ms
21,468 KB
input5.txt AC 128 ms
21,460 KB
input6.txt AC 130 ms
21,492 KB
input7.txt AC 127 ms
21,448 KB
input8.txt AC 122 ms
21,388 KB
input9.txt AC 128 ms
21,332 KB
input10.txt AC 129 ms
21,492 KB
input11.txt AC 131 ms
21,468 KB
input12.txt AC 126 ms
21,464 KB
input13.txt AC 127 ms
21,464 KB
input14.txt AC 126 ms
21,468 KB
input15.txt AC 129 ms
21,480 KB
input16.txt AC 129 ms
21,480 KB
input17.txt AC 127 ms
21,328 KB
input18.txt AC 122 ms
21,392 KB
input19.txt AC 126 ms
21,464 KB
input20.txt AC 125 ms
21,308 KB
input21.txt AC 177 ms
21,524 KB
sample1.txt AC 129 ms
21,188 KB
sample2.txt AC 121 ms
21,384 KB
sample3.txt AC 121 ms
21,380 KB
sample4.txt AC 121 ms
21,380 KB
system_test1.txt AC 127 ms
21,456 KB
system_test2.txt AC 120 ms
21,396 KB
system_test3.txt AC 128 ms
21,464 KB
system_test4.txt AC 117 ms
21,196 KB
テストケース一括ダウンロード

ソースコード

diff #
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main p = new Main();
	}

	public Main() {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int n = sc.nextInt();
		int[] c = new int[n];
		int[] v = new int[n];
		for(int i=0;i<n;i++)
			c[i] = sc.nextInt();
		
		for(int i=0;i<n;i++)
			v[i] = sc.nextInt();
		
		solve(t, c, v);
	}

	private void solve(int t, int[] c, int[] v) {
		int[] dp = new int[t+1];
		
		for(int i=0;i<c.length;i++){
			int cur = v[i];
			int count = 1;
			while(cur>0){
				for(int j=dp.length-1;j>=c[i]*count;j--){
					dp[j] = Math.max(dp[j], dp[j-c[i]]+cur);
				}
				cur /= 2;
			}
		}
		
		System.out.println(dp[t]);
	}
}
0