Cod sursa(job #806783)

Utilizator mipsPavel Mircea mips Data 3 noiembrie 2012 15:23:52
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

vector< pair<long long,long long> > values;
priority_queue<int> q;
int main()
{
    long long n,x,l,total=0;
    fin >> n >> x >>l;

    long long tmax=0;
    for (long long i=0;i<n;i++)
    {
        long long a,b;
        fin >> a >> b;
        values.push_back(make_pair((x-a)/l,b));
        tmax = max((x-a)/l,tmax);
    }
    //cout << tmax<<endl;
    sort(values.rbegin(),values.rend());
    int crt=0;
    for (long long i=tmax;i>=0;i--)
    {
        if (crt>=n)
            break;

        while (values[crt].first == i)
        {
            q.push(values[crt].second);
            //cout << "push"<< values[crt].second;
            crt++;
        }

        if (!q.empty())
        {
            total+= q.top();
            //cout << "total" <<total <<endl;
            q.pop();
        }
    }

    fout << total;
}
/*
0 1 2 3 4 5 6 7 8 9 10 11
3
10

1+a*3<=10
a*3<=9
a<=3
*/