Cod sursa(job #216225)

Utilizator ProtomanAndrei Purice Protoman Data 23 octombrie 2008 14:41:49
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <algorithm>
#define mx 110000
#define ll long long

using namespace std;

ll n, s, t, c, p, stdq = 1, sfdq = 1, cost;
pair <ll, ll> dq[mx];

int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%lld %lld %lld", &n, &s, &t);
	dq[stdq].first = 100 * mx;
	for (int i = 1; i <= n; i++)
	{
		if (dq[stdq].second < i - t)
			stdq++;
		scanf("%ld %ld", &c, &p);
		ll vl = min(c, dq[stdq].first + s * (i - dq[stdq].second));
		cost += (vl * p);
		dq[++sfdq].first = c;
		dq[sfdq].second = i;
		while (dq[sfdq].first < dq[sfdq - 1].first + s * (i - dq[sfdq - 1].second) && sfdq > stdq)
		{
			swap(dq[sfdq], dq[sfdq - 1]);
			sfdq--;
		}
	}
	printf("%lld", cost);
	fclose(stdin);
	fclose(stdout);
	return 0;
}