結果

問題 No.54 Happy Hallowe'en
コンテスト
ユーザー akakimidori
提出日時 2019-07-10 14:39:38
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 1,059 bytes
コンパイル時間 618 ms
コンパイル使用メモリ 30,464 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 13:07:22
合計ジャッジ時間 1,738 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))
#define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp)

typedef struct node {
  i32 v, t;
} node;

int cmp_node (const void *a, const void *b) {
  const node *p = a;
  const node *q = b;
  i32 x = MIN (p->t, q->t - p->v);
  i32 y = MIN (q->t, p->t - q->v);
  return x == y ? 0 : x > y ? -1 : 1;
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  node *p = ALLOC (n, node);
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32 "%" SCNi32, &p[i].v, &p[i].t);
  }
  SORT (p, n, cmp_node);
  const i32 m = 10000 * 2;
  uint8_t *ok = ALLOC (m + 1, uint8_t);
  ok[0] = 1;
  for (i32 i = 0; i < n; ++i) {
    i32 v = p[i].v;
    for (i32 j = p[i].t - 1; j >= 0; --j) {
      ok[j + v] |= ok[j];
    }
  }
  i32 ans = m;
  while (!ok[ans]) ans--;
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}
0