結果
問題 |
No.50 おもちゃ箱
|
ユーザー |
|
提出日時 | 2021-08-22 15:36:39 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,189 bytes |
コンパイル時間 | 483 ms |
コンパイル使用メモリ | 32,896 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-06 11:42:32 |
合計ジャッジ時間 | 1,579 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 2 |
other | AC * 4 WA * 34 |
コンパイルメッセージ
main.c: In function 'main': main.c:38:28: warning: passing argument 4 of 'qsort' from incompatible pointer type [-Wincompatible-pointer-types] 38 | qsort(b, M, sizeof(i64), comp); | ^~~~ | | | i64 (*)(const i64 *, const i64 *) {aka long int (*)(const long int *, const long int *)} In file included from main.c:2: /usr/include/stdlib.h:839:34: note: expected '__compar_fn_t' {aka 'int (*)(const void *, const void *)'} but argument is of type 'i64 (*)(const i64 *, const i64 *)' {aka 'long int (*)(const long int *, const long int *)'} 839 | __compar_fn_t __compar) __nonnull ((1, 4)); | ~~~~~~~~~~~~~~^~~~~~~~
ソースコード
#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; i64 comp(const i64 *a, const i64 *b) { i64 x = *(i64 *)a; i64 y = *(i64 *)b; return y - x; } 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]); } qsort(b, M, sizeof(i64), comp); 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; }