Cod sursa(job #2887495)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 9 aprilie 2022 18:45:25
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
#define cin f
#define cout g
const int Max = 1e5 + 1;

int n, s, t;
pair < int, int > d[Max];
int front, back;
long long ans = 0;

int cost_nou(pair < int, int > x, int i)
{
	return x.first + (i - x.second) * s;
}
int main()
{
	cin >> n >> s >> t;
	front = 1, back = 0;
	for(int i = 1; i <= n; i ++)
	{
		int cost, cantitate; 
		cin >> cost >> cantitate;
		if(front <= back)
			if(cost_nou(d[front], i) > cost)
				front = 1, back = 0;
		back ++;
		d[back].first = cost, d[back].second = i;
		ans += cost_nou(d[front], i) * cantitate;
		if(d[front].second + t == i)
		{
			front ++;
			for(int j = front + 1; j <= back; j ++)
				if(cost_nou(d[j], i) < cost_nou(d[front], i))
					front = j;
		}
	}
	cout << ans;
	return 0;
}