Cod sursa(job #962290)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 14 iunie 2013 14:57:21
Problema Branza Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
int v[100000],p[100000],coada[100000];
int main()
{
    FILE *fin,*fout;
    fin=fopen("branza.in","r");
    fout=fopen("branza.out","w");
    int n,s,k;
    fscanf(fin,"%d%d%d",&n,&s,&k);
    int i;
    for(i=0;i<n;i++)
        fscanf(fin,"%d%d",&v[i],&p[i]);
    long long S=0,st=1,dr=0;
    for(i=0; i<n; i++)
    {
        while(st<=dr&&v[i]*p[i]<=(i-coada[dr])*s*p[i]+p[i]*v[coada[dr]])
            dr--;
        dr++;
        coada[dr] = i;
        if (coada[st] == i-k)
            st++;
        S+=(i-coada[st])*s*p[i]+v[coada[st]]*p[i];
    }
    fprintf(fout,"%lld",S);
    return 0;
}