結果

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

ソースコード

diff #
raw source code 

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

perl -e '
use strict;
use warnings;

my $data = do { local $/; <STDIN> };
my $len = length($data);
my $pos = 0;

sub next_int {
  while ($pos < $len && ord(substr($data, $pos, 1)) <= 32) {
    ++$pos;
  }
  my $x = 0;
  while ($pos < $len) {
    my $c = ord(substr($data, $pos, 1));
    last if $c <= 32;
    $x = $x * 10 + $c - 48;
    ++$pos;
  }
  return $x;
}

sub bit_add {
  my ($bit, $n, $i, $delta) = @_;
  while ($i <= $n) {
    $bit->[$i] += $delta;
    $i += $i & -$i;
  }
}

sub bit_sum {
  my ($bit, $i) = @_;
  my $s = 0;
  while ($i > 0) {
    $s += $bit->[$i];
    $i -= $i & -$i;
  }
  return $s;
}

sub bit_kth {
  my ($bit, $n, $top, $k) = @_;
  my $idx = 0;
  my $step = $top;
  while ($step > 0) {
    my $nxt = $idx + $step;
    if ($nxt <= $n && $bit->[$nxt] < $k) {
      $idx = $nxt;
      $k -= $bit->[$nxt];
    }
    $step >>= 1;
  }
  return $idx + 1;
}

my $t = next_int();
my @ans;

for (1 .. $t) {
  my $n = next_int();
  my $k = next_int();

  my @a = map { next_int() } 1 .. $n;
  my @b = map { next_int() } 1 .. $n;
  my @c = map { next_int() } 1 .. $n;
  my @d = map { next_int() } 1 .. $n;

  my @vals = sort { $a <=> $b } (@a, @c);
  my @uniq;
  my %id;
  for my $v (@vals) {
    next if @uniq && $uniq[-1] == $v;
    push @uniq, $v;
    $id{$v} = scalar(@uniq);
  }

  my $m = scalar(@uniq);
  my @aid = map { $id{$_} } @a;
  my @cid = map { $id{$_} } @c;
  my @cnt = (0) x ($m + 1);
  my @bit = (0) x ($m + 1);

  my $top = 1;
  $top <<= 1 while (($top << 1) <= $m);

  my $total = 0;
  my $profit = 0;

  for (my $i = $n - 1; $i >= 0; --$i) {
    if ($d[$i] > 0) {
      my $idx = $cid[$i];
      $cnt[$idx] += $d[$i];
      bit_add(\@bit, $m, $idx, $d[$i]);
      $total += $d[$i];
    }

    my $buy_idx = $aid[$i];
    my $profitable = $total - bit_sum(\@bit, $buy_idx);
    my $take = $b[$i] < $profitable ? $b[$i] : $profitable;

    while ($take > 0) {
      my $best = bit_kth(\@bit, $m, $top, $total);
      my $use = $cnt[$best] < $take ? $cnt[$best] : $take;
      $cnt[$best] -= $use;
      bit_add(\@bit, $m, $best, -$use);
      $profit += ($uniq[$best - 1] - $a[$i]) * $use;
      $take -= $use;
      $total -= $use;

      $cnt[$buy_idx] += $use;
      bit_add(\@bit, $m, $buy_idx, $use);
      $total += $use;
    }

    my $excess = $total - $k;
    while ($excess > 0) {
      my $low = bit_kth(\@bit, $m, $top, 1);
      my $drop = $cnt[$low] < $excess ? $cnt[$low] : $excess;
      $cnt[$low] -= $drop;
      bit_add(\@bit, $m, $low, -$drop);
      $total -= $drop;
      $excess -= $drop;
    }
  }

  push @ans, $profit;
}

print join(qq{\n}, @ans), qq{\n};
'
0