Cod sursa(job #2852147)

Utilizator Kawaiimeatball13Russu Mihaela Kawaiimeatball13 Data 19 februarie 2022 11:40:54
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

deque <int> q;

int n, depozit, sapt;
int cost[100001], cantitate[100001];

void citire()
{
    fin >> n >> depozit >> sapt;
    for(int i = 0; i < n; ++i)
    {
        fin >> cost[i] >> cantitate[i];
    }
}

int pret(int i, int j)
{
    int p = (cost[j] + (i - j) * depozit);

    return p;
}

void adaugare(int i)
{
    while(!q.empty() &&  pret(i, q.back()) >= cost[i])
        q.pop_back();
    while(!q.empty() && (i - q.front()) > sapt)
            q.pop_front();
    q.push_back(i);
}

long long suma()
{
    long long s = 0;
    for(int i = 0; i < n; ++i)
    {
        adaugare(i);
        //cout << q.front() << ' ' << i << '\n';
        s += (cost[q.front()] + (i - q.front()) * depozit) * cantitate[i];
    }

    return s;
}

int main()
{
    citire();
    fout << suma();
    return 0;
}