Cod sursa(job #2117383)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 28 ianuarie 2018 20:21:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 100000
using namespace std;
int heap[MAXN],poz[MAXN],d[MAXN],el[MAXN],gr[MAXN],dim;
inline bool cmp(int x,int y)
{
    return gr[x]>gr[y];
}
inline void up(int p)
{
    int x;
    while((x=p>>1) && d[heap[p]]>d[heap[x]])
    {
        swap(poz[heap[p]],poz[heap[x]]);
        swap(heap[p],heap[x]);
        p=x;
    }
}
inline void down(int p)
{
    int x,maxim;
    bool ok=true;
    while((x=p<<1)<=dim && ok)
    {
        ok=false;
        if(x<dim && d[heap[x+1]]>d[heap[x]])
            maxim=x+1;
        else
            maxim=x;
        if(d[heap[maxim]]>d[heap[p]])
        {
            swap(poz[heap[maxim]],poz[heap[p]]);
            swap(heap[maxim],heap[p]);
            p=maxim;ok=true;
        }
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");
    int n,x,l,dist,grupa=0,i;
    long long s=0;
    fscanf(fin,"%d%d%d",&n,&x,&l);
    for(i=0;i<n;i++)
    {
        fscanf(fin,"%d%d",&dist,&d[i]);
        el[i]=i;
        if(x-dist>=0)
            gr[i]=(x-dist)/l+1;
        else
            gr[i]=0;
        grupa=max(grupa,gr[i]);
    }
    sort(el,el+n,cmp);
    i=0;
    for(;grupa;grupa--)
    {
        while(i<n && gr[el[i]]==grupa)
        {
            poz[el[i]]=++dim;heap[dim]=el[i];
            up(dim);i++;
        }
        if(dim)
        {
            s+=d[heap[1]];
            swap(poz[heap[1]],poz[heap[dim]]);
            swap(heap[1],heap[dim]);
            dim--;down(1);
        }
    }
    fprintf(fout,"%lld",s);
    fclose(fin);
    fclose(fout);
    return 0;
}