Cod sursa(job #2554531)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 23 februarie 2020 01:13:32
Problema Lupul Urias si Rau Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
using namespace std;

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

const int N = 100000;

struct oaie{
    int dist, lana;
} oi[N];

int h[N+1], grupa[N+1];
int nh;

void schimba(int p, int q){
    swap(h[p], h[q]);
}

bool compare(int p, int q){
    if(oi[h[p]].lana > oi[h[q]].lana)
        return true;
    else if(oi[h[p]].lana == oi[h[q]].lana && grupa[h[p]] > grupa[h[q]])
        return true;
    return false;
}

void urca(int p){
    while(p>1 && compare(p, p/2)){
        schimba(p, p/2);
        p /= 2;
    }
}

void coboara(int p){
    int fs = 2*p;
    int fd = 2*p+1;
    int bun = p;
    if(fs <= nh && compare(fs, bun))
        bun = fs;
    if(fd <= nh && compare(fd, bun))
        bun = fd;
    if(bun != p){
        schimba(p, bun);
        coboara(bun);
    }
}

void adauga(int x){
    h[++nh] = x;
    urca(nh);
}

void sterge(int p){
    schimba(p, nh--);
    urca(p);
    coboara(p);
}

bool cmp(oaie a, oaie b){
    if(a.dist < b.dist)
        return true;
    return false;
}

int main()
{
    int n,x,l,i,gr,timp,added;
    long long lana;
    fin >> n >> x >> l;
    for(i=0; i<n; i++)
        fin >> oi[i].dist >> oi[i].lana;
    sort(oi, oi+n, cmp);
    while(n>=0 && oi[n-1].dist > x)
        n--;
    gr = 0;
    for(i=0; i<n; i++){
        grupa[i] = (x - oi[i].dist) / l;
        gr = max(gr, grupa[i]);
        adauga(i);
    }
    lana = 0;
    for(i=0; i<=gr; i++){
        while(grupa[h[1]] < i)
            sterge(1);
        lana = lana + 1LL*oi[h[1]].lana;
        sterge(1);
    }
    fout << lana;
    return 0;
}