#699665 (C) No.50 おもちゃ箱

提出ソース

結果

問題	No.50 おもちゃ箱
ユーザー	kaoru murata
提出日時	2021-09-15 02:56:44
言語	C (gcc 12.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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 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) {
      |                     ~~~~~^

ソースコード

raw source code

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード