Cod sursa(job #2799069)

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

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

    int 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<int, int> > 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" );
    int n = readInt( fin );
    int s = readInt( fin );
    int k = readInt( fin );

    long long rez = 0;
    for( int i = 0; i < n; i++ ) {
        int cost = readInt( fin );
        int 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;
}