Cod sursa(job #2728650)

Utilizator ionut31Ioan Ionescu ionut31 Data 23 martie 2021 15:24:57
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

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


struct branza
{
    long long C, P;

};

int back = 0, front = 1;
int deque[100001];
branza v[100001];

void push_back(int x)
{
    ++back;
    deque[back] = x;
}

void pop_front()
{
    ++front;
}

void pop_back()
{
    --back;
}

int get_front()
{
    return deque[front];
}

int get_back()
{
    return deque[back];
}

bool is_Empty()
{
    return (front > back);
}

int main()
{
    long long N, T;
    int S;
    long long cost_total = 0;
    fin >> N >> S >> T;
    for(int i=0; i<N; ++i)
    {
        fin >> v[i].C >> v[i].P;
    }

    for(int i=0; i<N; ++i)
    {
        while(!is_Empty() && (i-get_front()) > T)
            pop_front();

        while(!is_Empty() && v[i].C < v[get_back()].C + S*(i-get_back()))
            pop_back();

        push_back(i);

        cost_total += v[i].P * (v[get_front()].C + S*(i-get_front()));
    }

    fout << cost_total;
    return 0;

}