Cod sursa(job #2799083)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 12 noiembrie 2021 12:14:44
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#include <deque>

std::deque<std::pair<long long, long long> > q;
long long n, k, s;

int main()
{
    FILE *fin = fopen( "branza.in", "r" );
    fscanf( fin, "%lld%lld%lld", &n, &s, &k );

    long long rez = 0, cost, kg;
    for( long long i = 0; i < n; i++ ) {
        fscanf( fin, "%lld%lld", &cost, &kg );

        while( !q.empty() && q.back().first + ( i - q.back().second ) * s > cost )
            q.pop_back();

        q.push_back( { cost, i } );
        if( q.front().second <= i - k )
            q.pop_front();
        rez += kg * ( q.front().first + ( i - q.front().second ) * s );
    }
    fclose( fin );

    FILE *fout = fopen( "branza.out", "w" );
    fprintf( fout, "%lld\n", rez );
    fclose( fout );
    return 0;
}