Cod sursa(job #3126380)

Utilizator theo_scrie_codGhinea Theodor theo_scrie_cod Data 6 mai 2023 16:35:47
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
#include <deque>
using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");
int v[100005];
int dequeMin[100005];
int kg[100005];

int main()
{
    int n, k,s;
    long long int sum = 0;
    in >> n >> s >> k;
    k++;
    deque<int> dq;


    for (int i = 1; i <= n; i++)
    {
        in >> v[i]>> kg[i];
    }

    int front= 1, back= 0;


	for (int i = 1; i <= n; i++)
    {   
        
        if (!dq.empty() && dq.front() == i - k)
            dq.pop_front();
        while (!dq.empty() && v[i] <= v[dq.back()] + s*(i - dq.back()))
            dq.pop_back();
        dq.push_back(i);
        sum += kg[i]*(v[dq.front()] + s*(i - dq.front()));

        
    }

    out << sum;

	return 0;
}