Cod sursa(job #3252919)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 31 octombrie 2024 15:06:49
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
//
//  main.cpp
//  lupul urias si rau
//
//  Created by Andrada Minca on 31.10.2024.
//

#include <bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,c,p,i,siz,k,d,j,a,l,vcc,x,val,v[100005],dist[100005],poz[100005];
struct hp
{
    int v;
    int p;
} heap[100005];
void myswap(int a, int b)
{
    swap(heap[a],heap[b]);
    swap(poz[heap[a].p],poz[heap[b].p]);
}
void uper(int po)
{
    while(heap[po].v>=heap[po/2].v&&po>1)
    {
        if((heap[po].v==heap[po/2].v&&dist[heap[po].p]>dist[heap[po/2].p])||heap[po].v>heap[po/2].v)
        myswap(po,po/2);
        po=po/2;
    }
}
void downy(int p)
{
    while(p*2<=siz)
    {
        int t=p*2;
        if(p*2<siz && heap[p*2+1].v>heap[p*2].v)t++;
        if(heap[p].v<heap[t].v){myswap(p,t);p=t;}
        if(heap[p].v==heap[t].v&&dist[heap[p].p]<dist[heap[t].p]){myswap(p,t);p=t;}
        else break;
    }
}
void add(int val,int p)
{
    siz++;
    heap[siz]={val,p};
    poz[p]=siz;
    uper(siz);
}
void del(int p)
{
    if(poz[p]==siz)siz--;
    else
    {
        int x=poz[p];
        myswap(poz[p],siz);
        siz--;
        uper(x);
        downy(x);
    }
}
int main() {
    fin>>n>>x>>l;
    x++;
    for(i=1;i<=n;i++)
    {
        fin>>d>>a;
        d++;
        add(a,i);
        dist[i]=d;

    }
    sort(v+1,v+n+1,greater<int>());
    int s=0,cop=x;
    while(x>=0)
    {
        int i=1,m=0;
        vcc=0;
        for(j=n;j>=1;j--)
        {
            if(dist[j]>x-l)vcc++;
            else break;
        }
        while(i<=cop/l+vcc)
        {
            if(dist[heap[i].p]>m&&dist[heap[i].p]<=x&&dist[heap[i].p]>0)val=heap[i].v,m=dist[heap[i].p];
            i++;
        }
        s+=val;
        x-=l;
    }
    fout<<s;
    return 0;
}