Cod sursa(job #962293)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 14 iunie 2013 15:05:57
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
long long v[100000],p[100000];
int coada[100000];
int main()
{
    FILE *fin,*fout;
    fin=fopen("branza.in","r");
    fout=fopen("branza.out","w");
    int n,k;
    long long s;
    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;
    k++;
    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;
}