Cod sursa(job #2912499)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 8 iulie 2022 18:02:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda 17_iulie Marime 1.85 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <algorithm>
#include <cstring>
#include <iomanip>


using namespace std;


//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("lupu.in");
ofstream g("lupu.out");

struct str{
    long long val;
    long long timp;
}v[100005];

long long n,x,l,k=0;
long long timpMax = -1;
long long sol = 0;

long long d,a;

long long h[100005],hk=0;

bool cmp(str a,str b){
    if(a.timp == b.timp){
        return a.val>b.val;
    }
    return a.timp>b.timp;
}

int main(){

    f>>n>>x>>l;
    for(int i=1;i<=n;i++){
        f>>d>>a;
        if(d<=x){
            k++;
            v[k].timp = (x-d)/l + 1;
            v[k].val = a;
            timpMax = max(timpMax,v[k].timp);
        }
    }
    sort(v+1,v+k+1,cmp);

    int j=1;
    for(int i=timpMax;i>=1;i--){

        while(j<=k && v[j].timp == i){

            ///punere in heap
            hk++;
            h[hk] = v[j].val;

            int tmp = hk;
            while(tmp>1 && h[tmp] > h[tmp/2]){
                swap(h[tmp],h[tmp/2]);
                tmp/=2;
            }



            j++;
        }

        if(hk>0){

            sol+=h[1];

            ///scoatere din heap

            h[1] = h[hk];
            hk--;

            int p=1,c=2;

            while(c<=hk){
                if(h[c]<h[c+1] && c+1<=hk){
                    c++;
                }
                if(h[c]>h[p]){
                    swap(h[c],h[p]);
                }else{
                    break;
                }

                p = c;
                c = 2*p;
            }
        }

        /*for(int y=1;y<=hk;y++){
            cout<<h[y]<<" ";
        }
        cout<<'\n';*/

    }

    g<<sol;

    f.close();
    g.close();
    return 0;
}