Cod sursa(job #2262501)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 17 octombrie 2018 15:23:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define N 100001
#define ll long long
ifstream in("lupu.in");
ofstream out("lupu.out");
pair<ll, ll> a[N];
ll p[N];
int main(){
    ll i,j,sum=0,n,s1=0,x,l,d;
    in>>n>>x>>l;
    for(i=1; i<=n; ++i){
        in>>d>>a[i].s;
        a[i].f=(x-d)/l+1;
        s1+=a[i].s;
    }
    sort(a+1, a+n+1);
    j=2;
    p[0]=-a[1].s;
    for(i=1; i<=a[n].f && j<=n; ++i){
        if(i>=a[j].f){
            if(a[j].s>-p[0]){
                sum-=p[0];
                pop_heap(p, p+i);
                --i;
                p[i]=-a[j].s;
                push_heap(p, p+i+1);
            }
            else
                sum+=a[j].s, --i;
            ++j;
        }
        else{
            p[i]=-a[j++].s;
            push_heap(p, p+i+1);
        }
    }
    out<<s1-sum;
    return 0;
}