Cod sursa(job #3341586)

Utilizator zionlyismAdobroaiei David zionlyism Data 20 februarie 2026 10:39:56
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>

#define NMAX 100002
#define INF 1e9
using namespace std;

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

struct oaie{int it, lana;};

int n, x, l;
oaie a[NMAX]; //a[i].it = la al catalea pas pot maxim sa o iau

bool compar(oaie a, oaie b)
{
    if(a.it == b.it) return a.lana > b.lana;
    return a.it < b.it;
}

int main()
{
    int i, d, aux;
    fin>>n>>x>>l;
    for(i = 1; i <= n; i++)
    {
        fin>>d>>aux;
        if(d > x) //oricum nu as putea sa o iau
        {
           a[i].it = INF;
           a[i].lana = -INF;
        }
        else
        {
           a[i].it = (x - d) / l + 1;
           a[i].lana = aux;
        }
    }
    //sortez crescator dupa .it si (in caz de egalitate) descrescator dupa .lana
    sort(a + 1, a + n + 1, compar);
    //for(i = 1; i <= n; i++) fout<<a[i].it<<' '<<a[i].lana<<'\n';
    long long int rez = 0;
    int last_it = 0;
    int extra = 0;
    for(i = 1; i <= n; i++)
    {
        if(last_it != a[i].it) //daca am ajuns la o valoarea noua a lui .it
        {
           if(extra) extra--;
           extra += (a[i].it - last_it - 1); //in cazul in care sar peste valori ale lui .it (pentru ca nu exista) atunci va trebui sa aleg mai multe dintre urmatoarele oi
           last_it = a[i].it;
           rez += a[i].lana;
        }
        else
        if(extra)
        {
           rez += a[i].lana;
           extra--;
        }
    }
    fout<<rez<<'\n';
    return 0;
}