結果

問題 No.3509 Get More Money
コンテスト
ユーザー Nakanishi Hiro
提出日時 2026-04-18 01:53:19
言語 Bash
(Bash 5.2.37)
コンパイル:
true
実行:
/usr/bin/bash _filename_
結果
TLE  
実行時間 -
コード長 4,838 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 187 ms
コンパイル使用メモリ 6,656 KB
実行使用メモリ 229,976 KB
最終ジャッジ日時 2026-04-18 01:53:54
合計ジャッジ時間 10,091 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env bash
set -euo pipefail

tmp_input="$(mktemp)"
tmp_vals="$(mktemp)"
tmp_sorted="$(mktemp)"
trap 'rm -f "$tmp_input" "$tmp_vals" "$tmp_sorted"' EXIT

cat >"$tmp_input"

awk '
function emit_token(x) {
  if (stage == 0) {
    stage = 1
  } else if (stage == 1) {
    n = x
    stage = 2
  } else if (stage == 2) {
    rem = n
    stage = 3
  } else if (stage == 3) {
    print x
    if (--rem == 0) {
      rem = n
      stage = 4
    }
  } else if (stage == 4) {
    if (--rem == 0) {
      rem = n
      stage = 5
    }
  } else if (stage == 5) {
    print x
    if (--rem == 0) {
      rem = n
      stage = 6
    }
  } else {
    if (--rem == 0) {
      stage = 1
    }
  }
}
{
  for (i = 1; i <= NF; ++i) emit_token($i + 0)
}
' "$tmp_input" >"$tmp_vals"

sort -n -u "$tmp_vals" >"$tmp_sorted"

awk -v vals_file="$tmp_sorted" '
function touch(node) {
  if (!(node in seen)) {
    seen[node] = 1
    touched[++tn] = node
  }
}

function clear_node(node) {
  touch(node)
  segcnt[node] = 0
  segsum[node] = 0
  seglazy[node] = 1
}

function push(node) {
  if (seglazy[node] == 0) return
  clear_node(node * 2)
  clear_node(node * 2 + 1)
  seglazy[node] = 0
}

function pull(node, left) {
  left = node * 2
  touch(node)
  segcnt[node] = segcnt[left] + segcnt[left + 1]
  segsum[node] = segsum[left] + segsum[left + 1]
}

function add_point(node, l, r, idx, delta, mid) {
  touch(node)
  if (l == r) {
    segcnt[node] += delta
    segsum[node] += vals[l] * delta
    seglazy[node] = 0
    return
  }
  push(node)
  mid = int((l + r) / 2)
  if (idx <= mid) add_point(node * 2, l, mid, idx, delta)
  else add_point(node * 2 + 1, mid + 1, r, idx, delta)
  pull(node)
}

function query_prefix_count(node, l, r, q, mid) {
  if (q < l || segcnt[node] == 0) return 0
  if (r <= q) return segcnt[node]
  push(node)
  mid = int((l + r) / 2)
  return query_prefix_count(node * 2, l, mid, q) + query_prefix_count(node * 2 + 1, mid + 1, r, q)
}

function remove_small(node, l, r, need, mid, left_take, ret) {
  if (need == 0 || segcnt[node] == 0) return 0
  if (need >= segcnt[node]) {
    ret = segsum[node]
    clear_node(node)
    return ret
  }
  if (l == r) {
    segcnt[node] -= need
    ret = vals[l] * need
    segsum[node] -= ret
    return ret
  }
  push(node)
  mid = int((l + r) / 2)
  left_take = need
  if (left_take > segcnt[node * 2]) left_take = segcnt[node * 2]
  ret = remove_small(node * 2, l, mid, left_take)
  ret += remove_small(node * 2 + 1, mid + 1, r, need - left_take)
  pull(node)
  return ret
}

function remove_large(node, l, r, need, mid, right_take, ret) {
  if (need == 0 || segcnt[node] == 0) return 0
  if (need >= segcnt[node]) {
    ret = segsum[node]
    clear_node(node)
    return ret
  }
  if (l == r) {
    segcnt[node] -= need
    ret = vals[l] * need
    segsum[node] -= ret
    return ret
  }
  push(node)
  mid = int((l + r) / 2)
  right_take = need
  if (right_take > segcnt[node * 2 + 1]) right_take = segcnt[node * 2 + 1]
  ret = remove_large(node * 2 + 1, mid + 1, r, right_take)
  ret += remove_large(node * 2, l, mid, need - right_take)
  pull(node)
  return ret
}

function reset_case(i, node) {
  for (i = 1; i <= tn; ++i) {
    node = touched[i]
    delete seen[node]
    delete segcnt[node]
    delete segsum[node]
    delete seglazy[node]
    delete touched[i]
  }
  tn = 0
  delete a
  delete b
  delete aid
  delete cid
  delete d
}

function solve_case(i, total, profit, profitable, take, removed, excess) {
  total = 0
  profit = 0
  for (i = n; i >= 1; --i) {
    if (d[i] > 0) {
      add_point(1, 1, m, cid[i], d[i])
      total += d[i]
    }

    profitable = total - query_prefix_count(1, 1, m, aid[i])
    take = b[i]
    if (take > profitable) take = profitable
    if (take > 0) {
      removed = remove_large(1, 1, m, take)
      profit += removed - a[i] * take
      add_point(1, 1, m, aid[i], take)
    }

    excess = total - k
    if (excess > 0) {
      remove_small(1, 1, m, excess)
      total -= excess
    }
  }
  print profit
  reset_case()
}

function process_token(x) {
  if (stage == 0) {
    t = x
    stage = 1
  } else if (stage == 1) {
    n = x
    stage = 2
  } else if (stage == 2) {
    k = x
    idx = 1
    stage = 3
  } else if (stage == 3) {
    a[idx] = x
    aid[idx] = id[x]
    if (idx++ == n) {
      idx = 1
      stage = 4
    }
  } else if (stage == 4) {
    b[idx] = x
    if (idx++ == n) {
      idx = 1
      stage = 5
    }
  } else if (stage == 5) {
    cid[idx] = id[x]
    if (idx++ == n) {
      idx = 1
      stage = 6
    }
  } else {
    d[idx] = x
    if (idx++ == n) {
      solve_case()
      stage = 1
    }
  }
}

BEGIN {
  while ((getline line < vals_file) > 0) {
    vals[++m] = line + 0
    id[line + 0] = m
  }
  close(vals_file)
  stage = 0
}

{
  for (i = 1; i <= NF; ++i) process_token($i + 0)
}
' "$tmp_input"
0