Cod sursa(job #2068181)

Utilizator mbanutaMihai Mihai mbanuta Data 17 noiembrie 2017 12:32:34
Problema Branza Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
#include <stdlib.h>

int d[100001];
int c[100001];
int p[100001];

int main()
{
    int n,t,st,dr,i,s;
    long long sum;
    sum=0;
    FILE*fin, *fout;
    fin = fopen ( "branza.in", "r" );
    fout = fopen ( "branza.out", "w" );
    st=0;
    dr=-1;
    fscanf( fin, "%d%d%d", &n, &s, &t );
    for( i = 0; i < n; i++ )
        fscanf( fin, "%d%d", &c[i], &p[i] );
    for( i = 0; i < n; i++ ){
        if( st <= dr && d[st] == i-t )
            st++;
        while( st <= dr && c[i] <= c[d[dr]] + (long long)s * (i-d[dr]) )
            dr--;
        d[++dr]=i;
        sum = sum + p[i] * (c[d[st]] + (long long)s * (i - d[st]) );
    }
    fprintf( fout, "%lld", sum );
    fclose( fin );
    fclose( fout );
    return 0;
}