Cod sursa(job #216224)

Utilizator ProtomanAndrei Purice Protoman Data 23 octombrie 2008 14:39:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <algorithm>
#define mx 110000

using namespace std;

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

int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%ld %ld %ld", &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);
		int 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("%ld", cost);
	fclose(stdin);
	fclose(stdout);
	return 0;
}