Cod sursa(job #1133022)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 4 martie 2014 11:51:59
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<fstream>
#include<algorithm>
#include<set>
#define NMAX 100010

using namespace std;

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

struct oaie
{
    int d, c;
}a[NMAX];
multiset<int> solutie, sl;
int n, L, x;

void Citeste()
{
    int i;

    f>>n>>x>>L;
    for (i=1; i<=n; ++i)
        f>>a[i].d>>a[i].c;
}

bool cmp(oaie A, oaie B)
{
    return A.d>B.d;
}

void Solve()
{
    int i=1, lg=1;
    multiset<int> :: iterator is, isolutie;

    sort(a+1, a+n+1, cmp);

    while (a[i].d>x) ++i;

    x-=L;

    while (i<=n && x>=-L)
    {
        while (i<=n && a[i].d>x)
        {
            if (solutie.size()<lg) solutie.insert(a[i].c);
            else
            {
                isolutie=solutie.begin();
                if (*isolutie<a[i].c)
                {
                    solutie.erase(isolutie);
                    solutie.insert(a[i].c);
                }
            }
            ++i;
        }
        ++lg; x-=L;
    }
}

void Scrie()
{
    multiset<int> :: iterator isolutie;
    long long x, sum=0;
    while (!solutie.empty())
    {
        isolutie=solutie.begin();
        x=*isolutie;
        sum+=x;
        solutie.erase(isolutie);
    }
    g<<sum<<"\n";
}

int main()
{
    Citeste();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}