Cod sursa(job #1321440)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 19 ianuarie 2015 09:36:06
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

struct Sheep
{
    int wool, time;
};

bool cmp(Sheep &s1, Sheep &s2);

int main()
{
    ifstream f("lupu.in");
    int N, X, L, D, A, i, k = 0;
    f >> N >> X >> L;
    Sheep s[N];
    int time = 0;
    for (i = 1; i <= N; i++)
    {
        f >> D >> A;
        if (D <= X)
        {
            s[k].time = (X - D) / L;
            s[k++].wool = A;
            if ((X - D) / L > time)
                time = (X - D) / L;
        }
    }
    f.close();

    sort(s, s + k, cmp);

    int k2 = 0;
    long long sum = 0;
    priority_queue<int> q;
    for (i = time; i >= 0; i--)
    {
        while(s[k2].time == i && k2 < k)
            q.push(s[k2++].wool);

        if (!q.empty())
        {
            sum += q.top();
            q.pop();
        }
    }

    ofstream g("lupu.out");
    g << sum;
    g.close();
    return 0;
}

bool cmp(Sheep &s1, Sheep &s2)
{
    return s1.time > s2.time;
}