Cod sursa(job #1115731)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 21 februarie 2014 23:39:29
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<stdio.h>
#define DIM 100005
FILE *f=fopen("branza.in","r"), *g=fopen("branza.out","w");

long long int n, s, t, i, p, u, C[DIM], P, Q[DIM], sum=0;

int main(){

    fscanf(f,"%lld %lld %lld\n",&n,&s,&t);
    p=1; u=0;
    for(i=1;i<=n;i++){

        fscanf(f,"%lld %lld\n",&C[i],&P);

        while( p<=u && C[i] <= C[ Q[u] ] + s*( i - Q[u] ) ) u--;
        Q[++u]=i;
        while( Q[p]+t < i ) p++;

        sum+= ( ( C[ Q[p] ]+ s * ( i - Q[p] ) ) * P );

    }
    fprintf(g,"%lld\n",sum);

return 0;
}