Cod sursa(job #3317090)

Utilizator Lex._.Lex Guiman Lex._. Data 22 octombrie 2025 10:14:00
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

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

struct oaie
{
    int dist=0, lana=0;
};

bool cmp(oaie a, oaie b) ///sorteaza oile descrescator dupa cantitatea de lana
{
    return (a.lana>b.lana);
}

oaie oi[NMAX];
int aint[NMAX*4]; ///arbore de intervale; pentru fiecare interval salvam cea mai mare pozitie care nu a fost ocupata pana acum

void build(int nod, int st, int dr) ///construim aint-ul
{
    if(st==dr)
    {
        aint[nod]=st;
        return;
    }
    int mij=st+(dr-st)/2;
    build(nod*2, st, mij);
    build(nod*2+1, mij+1, dr);
    aint[nod]=max(aint[nod*2], aint[nod*2+1]);
}

int query(int x, int y, int nod, int st, int dr) ///query aint; cauta cel mai mare element din intervalul [x, y]
{
    if(dr<x || st>y) return 0;
    if(x<=st && dr<=y) return aint[nod];
    int mij=st+(dr-st)/2;
    return max(query(x, y, nod*2, st, mij), query(x, y, nod*2+1, mij+1, dr));
}

void update(int poz, int val, int nod, int st, int dr) ///update aint
{
    if(st==dr)
    {
        aint[nod]=val;
        return;
    }
    int mij=st+(dr-st)/2;
    if(poz<=mij) update(poz, val, nod*2, st, mij); ///daca poz se afla in prima jumatate a intervalului
    else update(poz, val, nod*2+1, mij+1, dr); ///daca poz se afla in a doua jumatate a intervalului
    aint[nod]=max(aint[nod*2], aint[nod*2+1]);
}

int main()
{
    int n, x, l;
    in >> n >> x >> l;
    for(int i=1; i<=n; i++)
    {
        in >> oi[i].dist >> oi[i].lana;
    }
    sort(oi+1, oi+n+1, cmp);

    build(1, 1, n); ///construim aint-ul
    int suma=0; ///cantitatea maxima de lana pe care o poate aduna lupul
    for(int i=1; i<=n; i++)
    {
        if(x>oi[i].dist) ///daca se poate ajunge la oaie
        {
            int nr_ture=(x-oi[i].dist)/l+1; ///dupa cate ture nu se mai poate ajunge la oaie
            if(nr_ture<=n)
            {
                int poz=query(1, nr_ture, 1, 1, n); ///vom incerca sa luam oaie cat mai tarziu posibil (tura cat mai mare) ca sa lasam cat mai multe ture libere pentru oile care au distanta mai mica
                if(poz>0) ///daca se poate lua oaia
                {
                    update(poz, 0, 1, 1, n); ///marcam ca am luat deja o oaie in acea tura
                    suma+=oi[i].lana; ///adunam cantitatea de lana la suma
                }
            }
            else
            {
                suma+=oi[i].lana; ///adunam cantitatea de lana la suma
            }
        }
    }
    out << suma;

    return 0;
}