Cod sursa(job #3170806)

Utilizator Andrei_IgnatAndrei Ignat Andrei_Ignat Data 18 noiembrie 2023 10:09:50
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int main()
{   long long n , s , t , i , cantitate;
    f >> n >> s >> t;
    vector <long long> cost( n + 1 );
    long long costt = 0;
    deque <long long> dq;
    t++;
    for ( i = 0; i < n; i++ ){
        f >> cost[i] >> cantitate;
        while (( !dq.empty() )&&( dq.front() ==  i - t ))
            dq.pop_front();
        while (( !dq.empty() )&&( cost[i] <= cost[dq.back()] + ( i - dq.back() ) * s ))
            dq.pop_back();
        dq.push_back( i );
        costt += ( long long ) cantitate * ( cost[dq.front()] + ( i - dq.front() ) * s );
        ///cost[dq.front()] + ( i - dq.front() ) * s -> pretul mai ieftin
    }
    g << costt;
    return 0;
}