Cod sursa(job #2877451)

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

using namespace std;

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

map <int, long long> dp;

struct Sheep {
  int time;
  int 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() {

  int n, x, l;
  long long ans = 0;
  in >> n >> x >> l;
  for(int i = 1;i <= n;i++) {
    int dist, wool;
    in >> dist >> wool;
    int 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 + herd[i].wool);
          //cout << dp[it->first - 1] << ' ';
          ans = max(ans, dp[it->first - 1]);
        }
      }


    }

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