結果

問題 No.3509 Get More Money
コンテスト
ユーザー Enderaoe Lyther
提出日時 2026-04-17 22:38:28
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 1,897 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,392 ms
コンパイル使用メモリ 175,756 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2026-04-17 22:38:48
合計ジャッジ時間 14,678 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <map>
#include <string>
#include <vector>

using i64 = long long;
using i128 = __int128_t;

static void print_i128(i128 x) {
  if (x == 0) {
    std::cout << "0\n";
    return;
  }
  bool neg = false;
  if (x < 0) {
    neg = true;
    x = -x;
  }
  char buf[64];
  int n = 0;
  while (x > 0) {
    buf[n++] = char('0' + int(x % 10));
    x /= 10;
  }
  if (neg) {
    std::cout << '-';
  }
  while (n--) {
    std::cout << buf[n];
  }
  std::cout << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int T;
  std::cin >> T;
  while (T--) {
    int N;
    i64 K;
    std::cin >> N >> K;
    std::vector<i64> A(N), B(N), C(N), D(N);
    for (auto &x : A) {
      std::cin >> x;
    }
    for (auto &x : B) {
      std::cin >> x;
    }
    for (auto &x : C) {
      std::cin >> x;
    }
    for (auto &x : D) {
      std::cin >> x;
    }

    std::map<i64, i64> ms;
    i64 total = 0;
    i128 profit = 0;

    for (int i = 0; i < N; ++i) {
      i64 a = A[i], b = B[i], c = C[i], d = D[i];

      ms[-a] += b;
      total += b;

      i64 rem = d;
      while (rem > 0 && !ms.empty()) {
        auto it = std::prev(ms.end());
        i64 val = it->first;
        if (val + c <= 0) {
          break;
        }
        i64 cnt = it->second;
        i64 take = std::min(cnt, rem);
        profit += (i128)take * (i128)(val + c);
        if (cnt == take) {
          ms.erase(it);
        } else {
          it->second = cnt - take;
        }
        ms[-c] += take;
        rem -= take;
      }

      while (total > K && !ms.empty()) {
        auto it = ms.begin();
        i64 cnt = it->second;
        i64 drop = std::min(cnt, total - K);
        if (cnt == drop) {
          ms.erase(it);
        } else {
          it->second = cnt - drop;
        }
        total -= drop;
      }
    }

    print_i128(profit);
  }
  return 0;
}
0