Cod sursa(job #1281644)

Utilizator akaprosAna Kapros akapros Data 3 decembrie 2014 15:48:38
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,m,x,l,p,q,nr,Max,Min,N,k;
int X,Y;
long long sol;
struct nod
{
    int x;
    int y;
}v[100005];
int w[100005],W[100005],u[100005];
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d %d %d",&N,&x,&l);
    Min=2000000000;
    for (i=1;i<=N;i++)
    {
        scanf("%d %d",&X,&Y);
        if (X<=x)
        {
            v[++n].x=X,v[n].y=Y;
            p=v[i].x/l;
            if (v[i].x%l!=0)
            p++;
            Max=max(Max,p);
            if (p>=Max-N)
            Min=min(Min,p);
        }
    }
    k=Min;
    Max=Max-Min; Min=0;
    for (i=1;i<=n;i++)
    {
        p=v[i].x/l;
        if (v[i].x%l!=0)
        p++;
        p=p-k;
        if (w[p]<v[i].y)
        {
            u[W[p]]=0; u[i]=1;
            W[p]=i;
            w[p]=max(w[p],v[i].y);
        }
    }
    while ((x>0)&&(n>0))
    {
    for (i=Max;i>=Min;i--)
    sol=(sol+w[i])*1LL,x-=l;
    memset(w,0,sizeof(w));
    memset(W,0,sizeof(W));
    N=0;
    if (x)
    for (i=1;i<=n;i++)
    if ((!u[i])&&(v[i].x<=x))
    {
        v[++N]=v[i];
        p=v[i].x/l;
        if (v[i].x%l!=0)
        p++;
        if (w[p]<v[i].y)
        {
            u[W[p]]=0; u[i]=1;
            W[p]=i;
            w[p]=max(w[p],v[i].y);
        }
    }
    n=N;
    }
    printf("%lld",sol);
    return 0;
}