Cod sursa(job #2624458)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 4 iunie 2020 21:01:53
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

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

deque<pair<long long, long long>> DK;

int main()
{
    long long n, S, T, pret, cantitate;
    long long rez = 0;
    fin >> n >> S >> T;
    for(long long i = 1; i <= n; i++)
    {
        fin >> pret >> cantitate;
        while(!DK.empty() && DK.front().second < T - i)
            DK.pop_front();
        while(!DK.empty() && DK.back().first + (i - DK.back().second) * S >= pret)
            DK.pop_back();
        DK.push_back(make_pair(pret, i));
        rez += (DK.front().first + (i - DK.front().second) * S) * cantitate;
    }
    fout << rez;
    return 0;
}