Cod sursa(job #1997296)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 3 iulie 2017 21:04:52
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
// (C) 2017 Andrei Cotor. All rigths reserved.
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fi("lupu.in");
ofstream fo("lupu.out");
typedef struct sheep{int lana,timp;} SHEEP;
vector<int> Heap;
int dist,tmax,n,x,l,ind,rez,i;
SHEEP A[100001];

bool cmp(SHEEP a, SHEEP b)
{
    return a.timp>b.timp;
}

int main()
{
    fi>>n>>x>>l;
    for(i=1; i<=n; i++)
    {
        fi>>dist>>A[i].lana;
        A[i].timp=(x-dist)/l;
        tmax=max(tmax,A[i].timp);
    }
    sort(A+1,A+n+1,cmp);
    ind=1;
    for(i=tmax; i>=0; i--)
    {
        while(A[ind].timp==i && ind<=n)
        {
            Heap.push_back(A[ind].lana);
            push_heap(Heap.begin(),Heap.end());
            ind++;
        }
        if(!Heap.empty())
        {
            rez=rez+Heap.front();
            pop_heap(Heap.begin(),Heap.end());
            Heap.pop_back();
        }
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}