Cod sursa(job #960350)

Utilizator alecsandrualex cuturela alecsandru Data 10 iunie 2013 11:59:30
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
using namespace std;
int i;
struct branza
{
    int c,z;
};
branza dq[100100];
int st=1,dr=0,t,s,n,cant,cost,total;
void stanga()
{
    if(i-dq[st].z>t)
        st++;
}
void dreapta()
{
    while(dq[dr].c*cant+(i-dq[dr].z)*s*cant>cost*cant&&dr>=st)
    {
        dr--;
    }
    dq[++dr].c=cost;
    dq[dr].z=i;
}
int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    for(i=1;i<=n;i++)
    {
        stanga();
        scanf("%d%d",&cost,&cant);
        dreapta();
        total+=dq[st].c*cant;
        if(dq[st].z<i)
            total+=s*cant*(i-dq[st].z);
    }
    printf("%d",total);
    return 0;
}