Cod sursa(job #2307961)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 25 decembrie 2018 22:51:28
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.11 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

const int NMAX = 100000;

int N, D, L;
class Oaie
{
public:
    int timp, cant;
} A[NMAX+1];


priority_queue <int> oiCurr;


bool cmp( Oaie A, Oaie B )
{
    return A.timp < B.timp;
}

void Solve()
{
    int t_max = 0;

    for( int i = 1; i <= N; ++i )
        t_max = max( t_max, A[i].timp );

    sort(A+1, A + N + 1, cmp);

    int curr = N;
    long long sum = 0;

    for(int i = t_max; i > 0; i--)
    {
        while(A[curr].timp == i && curr > 0)
        {
            oiCurr.push(A[curr].cant);
            curr--;
        }

        if(oiCurr.size() > 0)
        {
            sum += oiCurr.top();
            oiCurr.pop();
        }
    }

    //for( int i = 1; i <= N; ++i )
    // fout << A[i].t << '\n';

    fout << sum << '\n';

    fout.close();
}

int main()
{
    fin >> N >> D >> L;

    int initDist;

    for( int i = 1; i <= N; i++)
    {
        fin >> initDist >> A[i].cant;
        A[i].timp = 1 + ( D - initDist ) / L;
    }

    fin.close();

    Solve();

    return 0;
}