Cod sursa(job #3126409)

Utilizator theo_scrie_codGhinea Theodor theo_scrie_cod Data 6 mai 2023 16:45:45
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 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++;


    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 (dequeMin[front] == i-k) front++;
        while(front <= back && v[i] - s*(i-dequeMin[back]) < v[dequeMin[back]])
            back--;

        back++;
        dequeMin[back]=i;
        

        sum += 1LL*kg[i] * (v[dequeMin[front]] +(i - dequeMin[front]) * s) ;

        
    }

    out << sum;

	return 0;
}