Cod sursa(job #1982074)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 17 mai 2017 17:40:48
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

ifstream fi("lupu.in");
ofstream fo("lupu.out");


void solve();

int n,x,l;
int sol, update;
int oi_lana[100001];
int oi_distanta[100001];
priority_queue< pair<int, int> > dist;///first distanta, second indice
priority_queue < pair<int, int> > lana;///first lana, second indice


int main()
{
    fi>>n>>x>>l;
    for(int i=1;i<=n;i++)
        fi>>oi_distanta[i]>>oi_lana[i];
    solve();
    fo<<sol;
    return 0;
}

void solve()
{
    for(int i=1;i<=n;i++)
        dist.push(make_pair(-oi_distanta[i],i));
    do{
        while(!dist.empty() && -dist.top().first + update <= x)
        {
            lana.push(make_pair(oi_lana[dist.top().second],dist.top().second));
            dist.pop();
        }

        sol+=lana.top().first;
        lana.pop();

        update += l;

        while(!lana.empty() && oi_distanta[lana.top().second]+update>x)
        {
            dist.push(make_pair(-oi_distanta[lana.top().second],lana.top().second));
            lana.pop();
        }
    }while(!lana.empty());

    return;
}