Cod sursa(job #2320750)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 15 ianuarie 2019 03:10:53
Problema Lupul Urias si Rau Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

priority_queue < int > myset;
pair <int,int> per[100010];
int main()
{
    int n,x,l,a,b;
    fin>>n>>x>>l;
     for(int i=1;i<=n;i++)
        fin>>per[i].first>>per[i].second;
    while(n && per[n].first>x) --n;
    sort(per,per+n+1);
    if(l==0)
    {
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
           // per[i].second=-per[i].second;
            if(per[i].first<=x) {sum=sum+per[i].second;}
        }

        fout<<sum;
        return 0;
    }


     int r=x%l,poz;

     for(int i=1;i<=n;i++)
        {
            if(per[i].first<=r) {myset.push(per[i].second);poz=i;}
        }

    long long sum = 0;
    if(myset.empty()==0) {sum=sum+myset.top();
                          myset.pop();
                         }
    int pasi=1;

    if(poz == n)
        pasi = 0;

    while(pasi<x/l+1&&poz<n)
    {
        for(int i=poz+1;i<=n;i++)
         if(per[i].first<=r+pasi*l) {poz=i;
                                     //myset.insert(per[i].second);
                                     myset.push(per[i].second);
                                    }
         else break;
        if(myset.empty()==0) {
                                sum=sum+myset.top();
                                myset.pop();
                             }
         int save=pasi;
        if(poz!=n)
         if(((per[poz+1].first)-r)%l==0) pasi=((per[poz+1].first)-r)/l;
         else  pasi=((per[poz+1].first)-r)/l+1;

         for(int i=1;i<pasi-save&&myset.empty()==0;i++)
         {
             sum=sum+myset.top();
             myset.pop();
         }


    //pasi++;
    }

    for(int i=1;i<=x/l-pasi&&myset.empty()==0;i++)
         {
             sum=sum+myset.top();
             myset.pop();
         }

    fout<<sum;
    return 0;
}