Cod sursa(job #1390035)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 16 martie 2015 20:07:46
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<stdio.h>
#define DIM 100005
FILE *f=fopen("branza.in","r"), *g=fopen("branza.out","w");

long long int i, N, T, C[DIM], S, P, Q[DIM], p, u, R=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;
        if( i - Q[p] > T ) p++;

        R += ( ( C[ Q[p] ] + S * ( i - Q[p] ) ) ) * P;
    }
    fprintf(g,"%lld\n",R);

return 0;
}