結果

問題 No.50 おもちゃ箱
ユーザー kaoru muratakaoru murata
提出日時 2021-09-15 02:56:44
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 5,369 bytes
コンパイル時間 1,089 ms
コンパイル使用メモリ 31,308 KB
実行使用メモリ 10,260 KB
最終ジャッジ日時 2023-09-10 07:32:37
合計ジャッジ時間 14,195 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘in’ 内:
main.c:36:14: 警告: 関数 ‘getchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   36 |   while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
      |              ^~~~~~~~~~~~~~~~
main.c: 関数 ‘out’ 内:
main.c:55:5: 警告: 関数 ‘putchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   55 |     putchar_unlocked('-');
      |     ^~~~~~~~~~~~~~~~
main.c: 関数 ‘main’ 内:
main.c:189:11: 警告: 互換性のないポインタ型から 1 番目の ‘radix32’ の引数に渡しています [-Wincompatible-pointer-types]
  189 |   radix32(B, M);
      |           ^
      |           |
      |           u64 * {aka long unsigned int *}
main.c:110:26: 備考: expected ‘i32 *’ {aka ‘int *’} but argument is of type ‘u64 *’ {aka ‘long unsigned int *’}
  110 | static void radix32(i32 *a, const i32 sz) {
      |                     ~~~~~^

ソースコード

diff # 

#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;
}
0