Cod sursa(job #1294267)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 17 decembrie 2014 10:20:46
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <stdio.h>
FILE *fin ,*fout;
#define N 100001
int st=1 ,dr=0 , d[N] , v[N] ,a[N] ,n ,k ,s;
void stanga (int i)
{
    if(i-d[st]==k)
    {
        st++;
    }
}
void dreapta (int i)
{
    while(st<=dr && v[i]<=v[d[dr]]+ s*(i-d[dr]))
    {
        dr--;
    }
    d[++dr]=i;
}
int main()
{
    fin = fopen("branza.in" ,"r");
    fout= fopen("branza.out" ,"w");
    int sum=0 ,i;
    fscanf(fin ,"%d%d%d" ,&n ,&s ,&k);
    for(i=1;i<=n;i++)
    {
        fscanf(fin ,"%d%d" ,&v[i] ,&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        stanga(i);
        dreapta(i);
        sum+=v[d[st]]*a[i] + s*(i-d[st]);
    }
    fprintf(fout ,"%d" ,sum);
    return 0;
}