結果
| 問題 |
No.50 おもちゃ箱
|
| コンテスト | |
| ユーザー |
 kaoru murata
|
| 提出日時 | 2021-09-15 02:56:44 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,369 bytes |
| コンパイル時間 | 247 ms |
| コンパイル使用メモリ | 33,024 KB |
| 実行使用メモリ | 6,656 KB |
| 最終ジャッジ日時 | 2024-06-27 23:03:03 |
| 合計ジャッジ時間 | 12,836 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | TLE * 1 -- * 37 |
コンパイルメッセージ
main.c: In function 'in':
main.c:36:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
36 | while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
| ^~~~~~~~~~~~~~~~
main.c: In function 'out':
main.c:55:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
55 | putchar_unlocked('-');
| ^~~~~~~~~~~~~~~~
main.c: In function 'main':
main.c:189:11: warning: passing argument 1 of 'radix32' from incompatible pointer type [-Wincompatible-pointer-types]
189 | radix32(B, M);
| ^
| |
| u64 * {aka long unsigned int *}
main.c:110:26: note: expected 'i32 *' {aka 'int *'} but argument is of type 'u64 *' {aka 'long unsigned int *'}
110 | static void radix32(i32 *a, const i32 sz) {
| ~~~~~^
ソースコード
#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#pragma region typedef
/* signed integer */
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef __int128_t i128;
/* unsigned integer */
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __uint128_t u128;
/* floating point number */
typedef float f32;
typedef double f64;
typedef long double f80;
#pragma endregion typedef
#pragma region io
static inline i64 in(void) {
i64 x = 0;
i64 f = 1;
i64 c;
while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
while (47 < c && c < 58) {
x = x * 10 + c - 48;
c = getchar_unlocked();
}
return f * x;
}
static inline u64 inU(void) {
u64 x = 0;
u64 c;
while (c = getchar_unlocked(), c < 48 || c > 57);
while (47 < c && c < 58) {
x = x * 10 + c - 48;
c = getchar_unlocked();
}
return x;
}
static inline void out(i64 x) {
if (x < 0) {
putchar_unlocked('-');
x = -x;
}
if (x >= 10) out(x / 10);
putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void outU(u64 x) {
if (x >= 10) outU(x / 10);
putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void nl(void) { putchar_unlocked('\n'); }
static inline void sp(void) { putchar_unlocked(' '); }
#pragma endregion io
#pragma region montgomery form
static inline u64 _inv(u64 mod) {
int i;
u64 u = 1;
u64 v = 0;
u64 x = 1ULL << 63;
for (int i = 0; i < 64; i++) {
if (u & 1){
u = (u + mod) / 2;
v = v / 2 + x;
} else {
u >>= 1;
v >>= 1;
}
}
return -v;
}
static inline u64 _one(u64 mod) { return -1ULL % mod + 1; }
static inline u64 _r2(u64 mod) { return (u128) (i128) -1 % mod + 1; }
static inline u64 _MR(u128 x, u64 inv, u64 mod) {
i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64);
return z < 0 ? z + mod : z;
}
static inline u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) { return _MR((u128)a * r2, inv, mod); }
static inline u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); }
static inline u64 addmod64(u64 x, u64 y, u64 mod) { return x + y >= mod ? x + y - mod : x + y; }
static inline u64 submod64(u64 x, u64 y, u64 mod) { return x >= y ? x - y : x - y + mod; }
static inline u64 mulmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); }
static inline u64 powmod64(u64 a, u64 n, u64 r2, u64 inv, u64 mod) {
u64 res = _one(mod);
u64 A = to_montgomery_form(a, r2, inv, mod);
while (n > 0) {
if (n & 1) res = _MR((u128)res * A, inv, mod);
A = _MR((u128)A * A, inv, mod);
n >>= 1;
}
return from_montgomery_form(res, inv, mod);
}
#pragma endregion montgomery form
#pragma region radix sort
static void radix32(i32 *a, const i32 sz) {
i32 shift = 0;
i32 elem[0x100];
i32 *aux = (i32 *)malloc(sizeof(i32) * sz);
i64 x = 0;
if (aux == NULL) { exit(EXIT_FAILURE); }
while (shift < 32) {
i32 bucket[0x100] = {0};
for (i32 i = 0; i < sz; i++) {
x = (a[i] >> shift) & 0xff;
bucket[x]++;
aux[i] = a[i];
}
elem[0] = 0;
for (i32 i = 0; i < 0xff; i++) { elem[i + 1] = elem[i] + bucket[i]; }
for (i32 i = 0; i < sz; i++) {
x = (aux[i] >> shift) & 0xff;
a[elem[x]] = aux[i];
elem[x]++;
}
shift += 8;
}
free(aux);
}
static void radix64(i64 *a, const i64 sz, const i64 minus) {
i64 shift = 0;
i64 sw = 0;
i64 elem[0x10000];
i64 *aux = (i64 *)malloc(sizeof(i64) * sz);
i128 x = 0;
if (aux == NULL) { exit(EXIT_FAILURE); }
while (shift < 64) {
i64 bucket[0x10000] = {0};
for (i64 i = 0; i < sz; i++) {
x = (a[i] >> shift) & 0xffff;
bucket[x]++;
aux[i] = a[i];
}
elem[0] = 0;
for (i64 i = 0; i < 0xffff; i++) { elem[i + 1] = elem[i] + bucket[i]; }
for (i64 i = 0; i < sz; i++) {
x = (aux[i] >> shift) & 0xffff;
a[elem[x]] = aux[i];
elem[x]++;
}
shift += 16;
}
free(aux);
for (i64 i = 0; i < (minus >> 1); i++) {
sw = a[sz - minus + i];
a[sz - minus + i] = a[sz - 1 - i];
a[sz - 1 - i] = sw;
}
for (i64 i = 0; i < ((sz - minus) >> 1); i++) {
sw = a[i];
a[i] = a[sz - minus - 1 - i];
a[sz - minus - 1 - i] = sw;
}
for (i64 i = 0; i < (sz >> 1); i++) {
sw = a[i];
a[i] = a[sz - 1 - i];
a[sz - 1 - i] = sw;
}
}
#pragma endregion radix sort
#define INF 1234567
u64 mini(u64 a, u64 b) {
if (a < b) return a;
return b;
}
int main() {
u64 u;
u64 A[11], B[11];
u64 N = inU();
for (u = 0; u < N; u++) A[u] = in();
u64 M = inU();
for (u = 0; u < M; u++) B[u] = in();
radix32(B, M);
u64 dp[1<<11] = {INF};
dp[0] = 0;
for (u64 i = 0; u < (1 << N); u++) {
if (dp[i] < M) {
for(u64 j = 0; u < (1 << N); j++) {
if (!(i & j)) {
u64 s = 0;
for (u64 k = 0; k < N; k++) {
if ((j >> k) & 1) s += A[k];
}
if (s <= B[M - 1 - dp[i]]) dp[i | j] = mini(dp[i | j], dp[i] + 1);
}
}
}
}
if (dp[1 << N - 1] == INF) putchar_unlocked('-'), putchar_unlocked('1'), nl();
else out(dp[1 << N - 1]), nl();
return 0;
}