Cod sursa(job #2724673)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 17 martie 2021 17:13:41
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "branza.in" );
ofstream fout( "branza.out" );

int N, S, T;
deque <pair<int, int> > Q;
long long cost;

int main()
{
    fin >> N >> S >> T;

    int p, demand;
    for( int i = 1; i <= N; ++i ) {
        fin >> p >> demand;

        while( !Q.empty() && ( i - Q.front().second ) > T )
            Q.pop_front();

        while( !Q.empty() && p < 1LL * Q.back().first + 1LL * S * ( i - Q.back().second ) )
            Q.pop_back();
        Q.push_back( { p, i } );

        cost += 1LL * demand * ( 1LL * Q.front().first + 1LL * S * ( i - Q.front().second ) );
    }

    fout << cost << '\n';
    return 0;
}