Cod sursa(job #1320129)

Utilizator IoanaMarMarussi Ioana IoanaMar Data 17 ianuarie 2015 17:19:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

int n, x, L, T = 0;
long long S = 0;
const int Max = 100100;
int O[Max];
int lana[Max];
int B[Max];
int ln2[Max];
int timp, ln;

priority_queue <int, vector<int> > Q;

void citire()
{
    f>>n>>x>>L;
    for(int i = 1; i <= n ; i++)
    {
        f>>timp>>lana[i];
        timp = 1 + (x - timp) / L;
        if(timp > T)
            T = timp;
        O[i] = timp;
    }
}

void merge_sort(int l, int r)
{
    int m = (l + r) >> 1, i, j, k;
    if (l == r)
        return;
    merge_sort(l, m);
    merge_sort(m + 1, r);
    for (i=l, j=m+1, k=l; i<=m || j<=r; )
        if (j > r || (i <= m && O[i] > O[j]))
        {
            B[k] = O[i];
            ln2[k++] = lana[i++];
        }
        else
        {
            B[k] = O[j];
            ln2[k++] = lana[j++];
        }
    for (k = l; k <= r; k++)
    {
        O[k] = B[k];
        lana[k] = ln2[k];
    }
}

void rezolva()
{
    int nr = 1, j = 0;
    for(int i = T ; i ; --i)
    {
        if(i == O[nr])
        {
            j = nr;
            while(O[j] == O[nr] && j <= n)
            {
                Q.push(lana[j]);
                j++;
            }
        }
        if(!Q.empty() )
        {
            S += Q.top();
            Q.pop();
        }
        nr = j;
    }
}

int main()
{
    citire();
    if(n == 1)
    {
        g<<lana[1];
        return 0;
    }
    merge_sort(1, n);
    rezolva();
    g<<S;

    return 0;
}