Cod sursa(job #2799073)

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

int type[ 100 ];
long long readInt( FILE *fin ) {
    long long rez = 0, ch;
    while( !type[ ( ch = fgetc( fin ) ) ] );

    long long semn = 1;
    if( ch == '-' ) {
        semn = -1;
        ch = fgetc( fin );
    }

    do
        rez = rez * 10 + ch - '0';
    while( type[ ( ch = fgetc( fin ) ) ] );

    return rez * semn;
}

std::deque<std::pair<long long, long long> > q;

int main()
{
    type[ '-' ] = type[ '0' ] = type[ '1' ] = type[ '2' ] = type[ '3' ] = type[ '4' ] = 1;
    type[ '5' ] = type[ '6' ] = type[ '7' ] = type[ '8' ] = type[ '9' ] = 1;
    
    FILE *fin = fopen( "branza.in", "r" );
    long long n = readInt( fin );
    long long s = readInt( fin );
    long long k = readInt( fin );

    long long rez = 0;
    for( int i = 0; i < n; i++ ) {
        long long cost = readInt( fin );
        long long kg = readInt( fin );

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

        q.push_back( { cost, i } );
        rez += kg * ( q.front().first + ( i - q.front().second ) * s );
    }
    FILE *fout = fopen( "branza.out", "w" );
    fprintf( fout, "%lld\n", rez );
    fclose( fout );
    return 0;
}