Cod sursa(job #2877462)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 24 martie 2022 19:26:53
Problema Lupul Urias si Rau Scor 28
Compilator cpp-64 Status done
Runda concursceva2 Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <map>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

typedef long long ll;

map <ll, long long> dp;

struct Sheep {
  ll time;
  ll wool;
};

bool compareSheep(Sheep a, Sheep b) {
  if(a.time == b.time){
    return (a.wool < b.wool);
  }
  return (a.time < b.time);
}

int const NMAX = 1e5;
Sheep herd[1 + NMAX];

int main() {

  long long n, x, l;
  long long ans = 0;
  in >> n >> x >> l;
  for(int i = 1;i <= n;i++) {
    long long dist, wool;
    in >> dist >> wool;
    long long time = (x - dist) / l + 1;
    herd[i].time = time;
    herd[i].wool = wool;
  }

  sort(herd+1, herd+n+1, compareSheep);

  for(int i = 1;i <= n;i++) {
    if(herd[i].time != 0) {
      auto it = dp.upper_bound(-herd[i].time);
      if(it == dp.end()) {
        if(it == dp.end()){
          dp[-1] = max(1LL * herd[i].wool, 1LL * dp[-1]);
          //cout << dp[-1] << ' ';
          ans = max(ans, dp[-1]);
        }
      }else {
        if(it == dp.end()){
          //cout << "it->first = 0\n";
          dp[-1] = max(1LL * herd[i].wool, 1LL * dp[-1]);
          //cout << dp[-1] << ' ';
          ans = max(ans, dp[-1]);
        }else {
          //cout << "it->first = "<< it->first << '\n';
          dp[it->first - 1] = max(dp[it->first - 1], it->second + 1LL * herd[i].wool);
          //cout << dp[it->first - 1] << ' ';
          ans = max(ans, dp[it->first - 1]);
        }
      }


    }

  }
  out << ans << '\n';
  return 0;
}