結果
問題 | No.617 Nafmo、買い出しに行く |
ユーザー | michonz4 |
提出日時 | 2019-12-26 14:46:05 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-14 23:56:07 |
合計ジャッジ時間 | 1,467 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 5 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 9 ms
6,940 KB |
testcase_06 | AC | 70 ms
6,940 KB |
testcase_07 | AC | 71 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 0 ms
6,944 KB |
testcase_10 | AC | 70 ms
6,940 KB |
testcase_11 | AC | 70 ms
6,944 KB |
testcase_12 | AC | 71 ms
6,944 KB |
testcase_13 | AC | 68 ms
6,940 KB |
testcase_14 | AC | 70 ms
6,944 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,940 KB |
ソースコード
/* No.617 Nafmo、買い出しに行く */ /* arr[]={1, 2, 3, 5}; 4種類の値(n)の組み合わせをbitで表現: 2*2*2*2=16 combination=0 < combination=16 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 論理積で1になった部分がそのiターンの重さになる, iターン内のiを合計してk以下なら解答の候補 i=0 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 0001 i=1 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 i=2 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 0100 i=3 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 iターンが終了したところでiターンの合計値sumとmaxを比較して最大値を保持する */ #include <stdio.h> int main() { int n, k, arrSize=0; scanf("%d %d", &n, &k); int arr[n], t; for (int i=0; i<n; i++) { scanf("%d", &t); if (t<=k) arr[arrSize++]=t; } int max=0; for (int combination=1; combination<(1<<arrSize); combination++) { int sum=0; for (int i=0; i<arrSize; i++) { if (combination&(1<<i)) { sum+=arr[i]; if (sum>k) break; } } if (sum<=k) max=(max>sum ? max: sum); } printf("%d\n", max); return 0; }