Cod sursa(job #1304750)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 29 decembrie 2014 11:28:13
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 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");
    long long sum=0;
    int 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+=(long long)(v[d[st]] + s*(i-d[st]))*a[i];
    }
    fprintf(fout ,"%lld" ,sum);
    return 0;
}