Cod sursa(job #2067091)

Utilizator alexburdescuBurdescu Alexandru alexburdescu Data 15 noiembrie 2017 20:22:43
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int N,dlup,doi;
struct oaie
{
    int dist,lana;
};
oaie heap[100009];
void urcare(oaie heap[], int p)
{
    while(p>=2 && heap[p].lana>heap[p/2].lana)
    {
        swap(heap[p],heap[p/2]);
        p=p/2;
    }
}
void coborare(oaie heap[] , int nh , int p)
{
    while(2*p<=nh)
    {
        int r=2*p;
        if(r+1<=nh && heap[r].lana<heap[r+1].lana)
        {
            r++;
        }
        if(heap[p].lana<heap[r].lana)
        {
            swap(heap[p],heap[r]);
            p=r;
        }
        else
        {
            break;
        }
    }
}
int main()
{
    fin>>N>>dlup>>doi;
    for(int i=1;i<=N;i++)
    {
        fin>>heap[i].dist>>heap[i].lana;
        urcare(heap , i);
    }
    int pas=0;
    int S=0;
    while(N!=0)
    {
        if(heap[1].dist+pas<dlup)
        {
            S=S+heap[1].lana;
            swap(heap[1],heap[N]);
            N--;
            coborare(heap,1,N);
        }
        else
        {
            swap(heap[1],heap[N]);
            N--;
            coborare(heap,1,N);
        }
        pas=pas+doi;
    }
    fout<<S;
    fin.close();
    fout.close();
    return 0;
}