Cod sursa(job #2117074)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 28 ianuarie 2018 14:53:04
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#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;
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("lupu.in","r");
    fout=fopen("lupu.out","w");
    int n,x,l,dist,grupa,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;
    }
    sort(el,el+n,cmp);
    i=0;grupa=1;
    while(!gr[el[i]])
        i++;
    for(;i<n;i++)
    {
        if(gr[el[i]]>grupa)
        {
            s+=1LL*d[heap[1]];
            grupa=gr[el[i]];dim=0;
        }
        poz[el[i]]=++dim;heap[dim]=el[i];
        up(dim);
    }
    fprintf(fout,"%lld",s+1LL*d[heap[1]]);
    fclose(fin);
    fclose(fout);
    return 0;
}