Cod sursa(job #2802966)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 19 noiembrie 2021 10:13:54
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#include <deque>

#define NMAXX 100000

using namespace std;

int v[NMAXX];
deque <long long> d;

int main()
{
    FILE *fin, *fout;
    int n, s, t, p, i;
    long long suma;

    fin = fopen( "branza.in", "r" );
    fout = fopen( "branza.out", "w" );

    fscanf( fin, "%d%d%d", &n, &s, &t );

    suma = 0LL;
    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%d%d", &v[i], &p );
        if ( !d.empty() && d.front() == i - t - 1 )
            d.pop_front();

        while ( !d.empty() && ( v[d.back()] + s * ( i - d.back() )) >= v[i] )
            d.pop_back();

        d.push_back( i );
        suma += ( (long long)v[d.front()] + s * ( i - d.front() ) ) * p;
    }

    fprintf( fout, "%lld", suma );
    fclose( fin );
    fclose( fout );
    return 0;
}