Cod sursa(job #3126397)

Utilizator theo_scrie_codGhinea Theodor theo_scrie_cod Data 6 mai 2023 16:41:54
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 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++)
    {   

        while(front <= back && v[i] - s*(back-front +1) < v[dequeMin[front]])
            front++;

        back++;
        dequeMin[back]=i;
        if (dequeMin[front] = i-k) front++;

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

        
    }

    out << sum;

	return 0;
}