提出 #65933842

ソースコード 拡げる

#include <stdio.h>

int N, X;
int S[8];
int C[8];
int P[8];

double memo[1 << 8][5123];
char memo_valid[1 << 8][5123];

double calc(int ac_list, int money) {
	double ans = 0;
	int i;
	if (memo_valid[ac_list][money]) return memo[ac_list][money];
	for (i = 0; i < N; i++) {
		if (!((ac_list >> i) & 1) && C[i] <= money) {
			double ac = calc(ac_list | (1 << i), money - C[i]) + S[i];
			double wa = calc(ac_list, money - C[i]);
			double candidate = (ac * P[i] + wa * (100 - P[i])) / 100;
			if (candidate > ans) ans = candidate;
		}
	}
	memo[ac_list][money] = ans;
	memo_valid[ac_list][money] = 1;
	return ans;
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &X) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d%d", &S[i], &C[i], &P[i]) != 3) return 1;
	}
	printf("%.20f\n", calc(0, X));
	return 0;
}

提出情報

提出日時
問題 E - Payment Required
ユーザ mikecat
言語 C (gcc 12.2.0)
得点 450
コード長 851 Byte
結果 AC
実行時間 61 ms
メモリ 13692 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 450 / 450
結果
AC × 4
AC × 43
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 02_random_30.txt, 02_random_31.txt, 02_random_32.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 1772 KiB
00_sample_01.txt AC 1 ms 1716 KiB
00_sample_02.txt AC 1 ms 1976 KiB
00_sample_03.txt AC 1 ms 2848 KiB
01_handmade_00.txt AC 1 ms 1756 KiB
01_handmade_01.txt AC 0 ms 1696 KiB
01_handmade_02.txt AC 1 ms 2100 KiB
01_handmade_03.txt AC 1 ms 2188 KiB
01_handmade_04.txt AC 61 ms 13692 KiB
01_handmade_05.txt AC 60 ms 13632 KiB
02_random_00.txt AC 1 ms 1756 KiB
02_random_01.txt AC 0 ms 1740 KiB
02_random_02.txt AC 1 ms 1788 KiB
02_random_03.txt AC 1 ms 1752 KiB
02_random_04.txt AC 1 ms 1668 KiB
02_random_05.txt AC 2 ms 2832 KiB
02_random_06.txt AC 1 ms 2464 KiB
02_random_07.txt AC 1 ms 2040 KiB
02_random_08.txt AC 4 ms 3276 KiB
02_random_09.txt AC 1 ms 1728 KiB
02_random_10.txt AC 1 ms 1816 KiB
02_random_11.txt AC 1 ms 1944 KiB
02_random_12.txt AC 14 ms 13272 KiB
02_random_13.txt AC 1 ms 1920 KiB
02_random_14.txt AC 1 ms 1820 KiB
02_random_15.txt AC 1 ms 1744 KiB
02_random_16.txt AC 1 ms 1748 KiB
02_random_17.txt AC 1 ms 1728 KiB
02_random_18.txt AC 1 ms 1812 KiB
02_random_19.txt AC 1 ms 2036 KiB
02_random_20.txt AC 38 ms 13380 KiB
02_random_21.txt AC 1 ms 1772 KiB
02_random_22.txt AC 1 ms 1904 KiB
02_random_23.txt AC 1 ms 1956 KiB
02_random_24.txt AC 1 ms 3408 KiB
02_random_25.txt AC 1 ms 2100 KiB
02_random_26.txt AC 61 ms 13688 KiB
02_random_27.txt AC 1 ms 2264 KiB
02_random_28.txt AC 61 ms 13528 KiB
02_random_29.txt AC 1 ms 1996 KiB
02_random_30.txt AC 60 ms 13620 KiB
02_random_31.txt AC 1 ms 1992 KiB
02_random_32.txt AC 61 ms 13652 KiB