Cod sursa(job #148575)

Utilizator radamiRadu Patulescu radami Data 4 martie 2008 15:51:11
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>

long long n,s,t,cant[100010],cost[100010],pret[100010];
long long coada[100010],nr = 1,start = 1,exp[100010],total;

int main ()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	
	scanf("%lld %lld %lld",&n,&s,&t);
	for (int i = 1;i <=n; i++)
		{
			scanf("%lld %lld",&pret[i],&cant[i]);
			cost[i] = pret[i] + (n - i) * 10;
		}
	
	coada[1] = cost[1];
	exp[1] = 1 + t;
	total = cant[1] * pret[1];
	for (int i = 2;i <= n; i++)
	{
		if (exp[start] == i)
			start++;
		int adaugat = 0;
		for (int j = nr;j >= start; j--)
			if (cost[i] < coada[j])
					{
						coada[j] = cost[i];
						exp[j] = i + t;
						adaugat = 1;
					}
			else break;
		if (!adaugat)
			{
				coada[++nr] = cost[i];
				exp[nr] = i + t;
			}
			
		total += (coada[start] - s * (n - i)) * cant[i];
	}
		
	printf("%lld",total);
	
	
	
	
	return 0;
}