結果

問題 No.1739 Princess vs. Dragoness (& AoE)
ユーザー yuly3yuly3
提出日時 2021-11-27 13:37:59
言語 Nim
(2.0.2)
結果
AC  
実行時間 1,057 ms / 3,000 ms
コード長 4,700 bytes
コンパイル時間 4,013 ms
コンパイル使用メモリ 68,576 KB
実行使用メモリ 6,928 KB
最終ジャッジ日時 2023-09-12 15:57:11
合計ジャッジ時間 21,954 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 627 ms
5,584 KB
testcase_05 AC 1,057 ms
6,740 KB
testcase_06 AC 442 ms
6,928 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 271 ms
4,532 KB
testcase_09 AC 331 ms
4,628 KB
testcase_10 AC 316 ms
4,376 KB
testcase_11 AC 175 ms
4,380 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 373 ms
4,572 KB
testcase_14 AC 659 ms
5,296 KB
testcase_15 AC 547 ms
5,604 KB
testcase_16 AC 470 ms
4,376 KB
testcase_17 AC 270 ms
4,436 KB
testcase_18 AC 521 ms
4,476 KB
testcase_19 AC 62 ms
4,376 KB
testcase_20 AC 117 ms
4,380 KB
testcase_21 AC 242 ms
4,700 KB
testcase_22 AC 518 ms
5,480 KB
testcase_23 AC 567 ms
5,572 KB
testcase_24 AC 1,005 ms
5,744 KB
testcase_25 AC 932 ms
5,528 KB
testcase_26 AC 639 ms
6,748 KB
testcase_27 AC 1,010 ms
5,680 KB
testcase_28 AC 662 ms
6,728 KB
testcase_29 AC 1,012 ms
5,600 KB
testcase_30 AC 694 ms
5,708 KB
testcase_31 AC 727 ms
6,796 KB
testcase_32 AC 1,031 ms
6,764 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,380 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 3 ms
4,380 KB
testcase_39 AC 3 ms
4,376 KB
testcase_40 AC 2 ms
4,380 KB
testcase_41 AC 3 ms
4,376 KB
testcase_42 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(5, 5) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(6, 5) Warning: imported and not used: 'bitops' [UnusedImport]
/home/judge/data/code/Main.nim(15, 5) Warning: imported and not used: 'sugar' [UnusedImport]
/home/judge/data/code/Main.nim(12, 5) Warning: imported and not used: 'sequtils' [UnusedImport]
/home/judge/data/code/Main.nim(13, 5) Warning: imported and not used: 'strformat' [UnusedImport]

ソースコード

diff # 

when not declared ATCODER_YULY3HEADER_HPP:
  const ATCODER_YULY3HEADER_HPP* = 1

  import
    algorithm,
    bitops,
    deques,
    heapqueue,
    math,
    macros,
    sets,
    sequtils,
    strformat,
    strutils,
    sugar,
    tables

  proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
    # Looks for the last statement of the last statement, etc...
    case n.kind
    of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      for i in ord(n.kind == nnkCaseStmt)..<n.len:
        (result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
    of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
        nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      if n.len >= 1:
        (result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],
            res, bracketExpr)
    of nnkTableConstr:
      result[1] = n[0][0]
      result[2] = n[0][1]
      if bracketExpr.len == 1:
        bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
            bindSym"typeof", newEmptyNode())])
      template adder(res, k, v) = res[k] = v
      result[0] = getAst(adder(res, n[0][0], n[0][1]))
    of nnkCurly:
      result[2] = n[0]
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.incl(v)
      result[0] = getAst(adder(res, n[0]))
    else:
      result[2] = n
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.add(v)
      result[0] = getAst(adder(res, n))

  macro collect*(init, body: untyped): untyped =
    runnableExamples:
      import sets, tables
      let data = @["bird", "word"]
      ## seq:
      let k = collect(newSeq):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert k == @["bird"]
      ## seq with initialSize:
      let x = collect(newSeqOfCap(4)):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert x == @["bird"]
      ## HashSet:
      let y = initHashSet.collect:
        for d in data.items: {d}
      assert y == data.toHashSet
      ## Table:
      let z = collect(initTable(2)):
        for i, d in data.pairs: {i: d}
      assert z == {0: "bird", 1: "word"}.toTable

    let res = genSym(nskVar, "collectResult")
    expectKind init, {nnkCall, nnkIdent, nnkSym}
    let bracketExpr = newTree(nnkBracketExpr,
      if init.kind == nnkCall: init[0] else: init)
    let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
    if bracketExpr.len == 3:
      bracketExpr[1][1] = keyType
      bracketExpr[2][1] = valueType
    else:
      bracketExpr[1][1] = valueType
    let call = newTree(nnkCall, bracketExpr)
    if init.kind == nnkCall:
      for i in 1 ..< init.len:
        call.add init[i]
    result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)

  proc nextString*(f: auto = stdin): string =
    var get = false
    result = ""
    while true:
      let c = f.readChar
      if c.int > ' '.int:
        get = true
        result.add(c)
      elif get: return
  proc nextInt*(f: auto = stdin): int = parseInt(f.nextString)
  proc nextFloat*(f: auto = stdin): float = parseFloat(f.nextString)

  proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)
  proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)
  proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)
  proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or m
  proc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and m
  proc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor m
  proc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl m
  proc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr m

when isMainModule:
  var
    N, A, B, X, Y = nextInt()
    H: array[100001, int]
  for i in 0..<N:
    H[i] = nextInt()

  var HP = initHeapQueue[int]()

  proc f(t: int): bool =
    for i in 0..<N:
      if H[i] - t > 0:
        HP.push(-H[i] + t)
    for _ in 0..<A:
      if HP.len() == 0:
        return true
      var mx = -HP.pop()
      mx -= X
      if mx > 0:
        HP.push(-mx)
    var sm = 0
    while HP.len() > 0:
      sm += -HP.pop()
    return sm <= B*Y

  var (ok, ng) = (10^9, -1)
  while ok - ng > 1:
    let med = (ok + ng) shr 1
    if f(med):
      ok = med
    else:
      ng = med
  echo ok
0