#1181051 (C++23(gcc16)) No.3656 Game Scores and Costs

• 問題: No.3656 Game Scores and Costs
• ユーザー: ei1333333
• 提出日時: 2026-08-30 14:34:33
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 33 ms / 2,000 ms
• コード長: 4,226 bytes
• コンパイル時間: 4,568 ms
• コンパイル使用メモリ: 390,256 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 14:34:42
• 合計ジャッジ時間: 7,038 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}

#line 2 "structure/others/priority-sum-structure.hpp"

#include <cassert>
#include <cstddef>
#include <functional>
#include <queue>
#include <vector>

template <typename T, typename Compare = std::less<T>,
          typename RCompare = std::greater<T>>
struct PrioritySumStructure {
  std::size_t k;
  T sum;

  std::priority_queue<T, std::vector<T>, Compare> in, d_in;
  std::priority_queue<T, std::vector<T>, RCompare> out, d_out;

  PrioritySumStructure(int k) : k(k), sum(0) {}

  void modify() {
    while (in.size() - d_in.size() < k && !out.empty()) {
      auto p = out.top();
      out.pop();
      if (!d_out.empty() && p == d_out.top()) {
        d_out.pop();
      } else {
        sum += p;
        in.emplace(p);
      }
    }
    while (in.size() - d_in.size() > k) {
      auto p = in.top();
      in.pop();
      if (!d_in.empty() && p == d_in.top()) {
        d_in.pop();
      } else {
        sum -= p;
        out.emplace(p);
      }
    }
    while (!d_in.empty() && in.top() == d_in.top()) {
      in.pop();
      d_in.pop();
    }
  }

  T query() const { return sum; }

  T kth_element() {
    assert(0 < k && k <= size());
    modify();
    return in.top();
  }

  void insert(T x) {
    in.emplace(x);
    sum += x;
    modify();
  }

  void erase(T x) {
    assert(size());
    if (!in.empty() && in.top() == x) {
      sum -= x;
      in.pop();
    } else if (!in.empty() && RCompare()(in.top(), x)) {
      sum -= x;
      d_in.emplace(x);
    } else {
      d_out.emplace(x);
    }
    modify();
  }

  void set_k(std::size_t kk) {
    k = kk;
    modify();
  }

  std::size_t get_k() const { return k; }

  std::size_t size() const {
    return in.size() + out.size() - d_in.size() - d_out.size();
  }
};

template <typename T>
using MaximumSum = PrioritySumStructure<T, std::greater<T>, std::less<T>>;

template <typename T>
using MinimumSum = PrioritySumStructure<T, std::less<T>, std::greater<T>>;


int main() {
  int N, K, X;
  cin >> N >> K >> X;
  MaximumSum< int64 > que{1};
  int64 ret = -infll;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    que.insert(a);
    que.set_k(min(i + 1, K));
    chmax(ret, que.query() - 1ll * X * (i + 1));
  }
  cout << ret << "\n";
}