結果
問題 |
No.50 おもちゃ箱
|
ユーザー |
|
提出日時 | 2021-08-22 15:17:02 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,342 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 32,768 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-06 11:24:44 |
合計ジャッジ時間 | 1,949 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 2 |
other | AC * 5 WA * 33 |
ソースコード
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <stdbool.h> #include <time.h> #include <math.h> #include <assert.h> typedef int64_t i64; typedef uint64_t u64; typedef __int128_t i128; typedef __uint128_t u128; void bucket_sort(i64 arr[], i64 sz) { i64 buckets[21]; i64 i; for (i = 0; i < 21; i++) buckets[i] = 0; for (i = 0; i < sz; i++) buckets[arr[i]] = arr[i]; i64 j = 0; for (i = 0; i < 21; i++) if (0 < buckets[i]) arr[j++] = buckets[i]; } int main() { int i, j, k; int N; scanf("%d", &N); i64 a[N]; for (i = 0; i < N; i++) { scanf("%ld", &a[i]); } int M; scanf("%d", &M); i64 b[M]; for (i = 0; i < M; i++) { scanf("%ld", &b[i]); } bucket_sort(b, M); bool dp1[1 << 10]; bool dp2[1 << 10]; dp1[0] = true; for (i = 0; i < M; i++) { for (j = 0; j < (1 << N); j++) { i64 c = 0; for (k = 0; k < N; k++) { if ((j >> k) % 2 == 0) continue; c += a[k]; } if (c > b[M - 1 - i]) continue; for (k = (1 << N) - 1; k >= 0; k--) { dp2[j | k] |= dp1[k]; } } for (k = (1 << N) - 1; k >= 0; k--) { dp1[k] = dp2[k]; } if (dp1[(1 << N) - 1]) { printf("%d\n", i + 1); return 0; } } printf("-1\n"); return 0; }