Cod sursa(job #599792)

Utilizator Catah15Catalin Haidau Catah15 Data 29 iunie 2011 16:38:01
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>

using namespace std;

#define maxN 100005
#define LL long long

LL D[maxN], C[maxN], P[maxN];
LL sol;


int main()
{
	freopen ("branza.in", "r", stdin);
	freopen ("branza.out", "w", stdout);
	
	int N, S, T;
	
	scanf ("%d %d %d", &N, &S, &T);
	
	for (int i = 1; i <= N; ++ i) scanf ("%d %d", &C[i], &P[i]);
	
	int st = 1, dr = 0;
	
	for (int i = 1; i <= N; ++ i)
	{
		if (st <= dr && i - D[st] > T) ++ st;
		
		while (st <= dr && C[D[dr]] + (i - D[dr]) * S > C[i]) -- dr;
		
		D[++ dr] = i;
		
		sol += (C[D[st]] + (i - D[st]) * S) * P[i];
	}
	
	printf ("%lld", sol);
	
	return 0;
}