Cod sursa(job #2031841)

Utilizator cameleonGeorgescu Dan cameleon Data 3 octombrie 2017 21:42:53
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;
#define NMAX 100005

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

struct oaie{
    int strat, lana;
};
oaie v[NMAX];
int n, X, L;
priority_queue <int> q;
bool cmp(oaie a, oaie b){
    return a.strat>b.strat;
}
void citire(){
    int distanta, cant, k=0;
    fin>>n>>X>>L;
    for(int i=1;i<=n;i++){
        fin>>distanta>>cant;
        if(distanta<=X){
        //strarturile sunt numerotate cu 1,2,...X/L+1 de la exterior spre interior
            v[++k].strat=(X-distanta)/L+1;
            v[k].lana=cant;
        }
    }
    n=k;
}
int main()
{
    citire();
    sort(v+1,v+n+1,cmp);
    long long total = 0;
    int  j=1;//indica oaia curenta
    for(int i=X/L+1;i>=1;i--)// iau pe rand oi de pe fiecare strat
    {
            while(j<=n && v[j].strat==i){
               q.push(v[j].lana);
               j++;
            }
            if(!q.empty()){
                total+=q.top();
                q.pop();
            }
    }
    fout<<total;
    return 0;
}