Cod sursa(job #2174808)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 16 martie 2018 13:35:40
Problema Branza Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100000

int c[N], p[N], dq[N];
int prim = 0, ultim = -1;

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