Cod sursa(job #3351501)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 19 aprilie 2026 19:44:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cassert>

#include <algorithm>
#include <vector>

#include <set>

template<class T> using vec = std::vector<T>;
using ll = long long;

int main() {
  std::ifstream fin("lupu.in");
  std::ofstream fout("lupu.out");

  int n, step, range;
  fin >> n >> range >> step;

  vec<std::pair<int, int>> oi(n); {
    for( auto &[x, cost]: oi )
      fin >> x >> cost;
    std::sort( oi.begin(), oi.end() );
  }

  std::multiset<int> costs;
  for( int i = 0; i < n; i++ ){
    costs.insert( oi[i].second );
    int turnsA = (step + std::max( -1, range - oi[i].first )) / step;
    int turnsB = (i + 1 == n ? 0 : (step + std::max( -1, range - oi[i + 1].first )) / step);
    int dturns = std::min( turnsA - turnsB, (int)costs.size() );

    for( int t = 0; t < dturns; t++ )
      costs.erase( std::prev( costs.end() ) );
  }

  ll ret = 0;
  for( const auto &[x, cost]: oi ) ret += cost;
  for( int cost : costs ) ret -= cost;
  fout << ret << std::endl;
  return 0;
}