Cod sursa(job #911378)

Utilizator assa98Andrei Stanciu assa98 Data 11 martie 2013 16:20:15
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>

struct sp
{
    long long cost;
    long long count;
} d[100100];

int s,t;

long long sol;

int beg;
int end;

void pop_front()
{
    sol+=d[beg].cost*d[beg].count;
    beg++;
}

void print()
{
    for(int i=beg;i<=end;i++)
        printf("%d ",d[i].cost);
    printf("\n");
    for(int i=beg;i<=end;i++)
        printf("%d ",d[i].count);
    printf("\n");
    printf("\n");
}


int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    int n;
    scanf("%d%d%d",&n,&s,&t);
    beg=1;
    for(int i=1;i<=n;i++)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        d[++end].cost=a;
        d[end].count=b;
        if(end-beg+1>t)
        {
            pop_front();
        }
        //print();
        while(end>beg &&
              d[beg].cost*b+(end-beg)*s*b>d[end].cost*d[end].count)
              {
                  pop_front();
              }
        if(beg<end)
        {
            d[beg].count+=d[end].count;
            d[end].count=0;
            sol+=(end-beg)*s*b;
        }
        //print();
    }
    while(beg<=end)
        pop_front();
    printf("%lld",sol);
    return 0;
}