Cod sursa(job #357594)

Utilizator iulia609fara nume iulia609 Data 19 octombrie 2009 20:39:59
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
#define dim 100001
using namespace std;

long long C[dim], deq[dim], P[dim]; 

int main()
{ long long N,S,T,vf,k,i,rez;
	
	FILE *f = fopen("branza.in", "r");
	FILE *g = fopen("branza.out", "w");
	
	fscanf(f, "%lld %lld %lld", &N, &S, &T);
	
	vf = 1; k = rez = 0;
	for(i = 1; i <= N; i++)
		{
			fscanf(f, "%lld%lld", &C[i], &P[i]);
			if(i - deq[vf] > T) vf++;
			while(C[i] <= C[deq[k]] + S*(i-deq[k])) 
				if(k >= vf)
					k--;
				  else break;
			
			deq[++k] = i;
			rez += P[i] * (C[deq[vf]] + S * (i - deq[vf]));
		}
	
	fprintf(g, "%lld\n", rez);
	
	fclose(f);
	fclose(g);
	return 0;
}