Cod sursa(job #811883)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 13 noiembrie 2012 09:17:01
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>

#define maxn 100005

FILE*f=fopen("branza.in","r");
FILE*g=fopen("branza.out","w");

int n,s,T;
int deque[maxn],front,back,P[maxn];
long long D[maxn];

int main () {
	
	fscanf(f,"%d %d %d",&n,&s,&T);
	int pret,cerere;
	int front = 1,back = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		
		fscanf(f,"%d %d",&pret,&cerere); P[i] = pret;
		while ( front <= back && 1LL*(i-deque[back])*s + P[deque[back]] >= pret ){
			deque[back--] = 0;
		}
		deque[++back] = i;
		if ( deque[front] < i-T ){
			++front;
		}
		
		D[i] = D[i-1] + 1LL*cerere*( 1LL*(i-deque[front])*s + P[deque[front]] );
	}
	
	fprintf(g,"%lld\n",D[n]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}