Cod sursa(job #2729059)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 24 martie 2021 01:18:27
Problema Branza Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <deque>

#define v first
#define s second

using namespace std;

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

long long N, K, T;
long long c, p;
long long S;

deque < pair < long long, long long > > B;

void Solve()
{
    fin >> N >> K >> T;

    int cost;

    for( int i = 1; i <= N; ++i )
    {
        fin >> c >> p;
        cost = c;

        while( !B.empty() )
        {
            if( i - B.front().s <= T && B.front().v + (i - B.front().s) * K < cost)
            {
                cost = B.front().v + (i - B.front().s) * K;
                break;
            }
            B.pop_front();
        }

        while( !B.empty() && B.back().v + (i - B.front().s) * K > c )
            B.pop_back();

        B.push_back( {c,i} );
        S += 1LL*cost*p;
    }

    fout << S;
}
int main()
{
    Solve();
    return 0;
}