Cod sursa(job #1364671)

Utilizator BLz0rDospra Cristian BLz0r Data 27 februarie 2015 19:31:19
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
#include <deque>
using namespace std;

#define Nmax 100002

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

deque < int > Q;

int a[Nmax], b[Nmax];

int main(){
	int N, S, T;
	long long total = 0;
	
	fscanf ( f, "%d%d%d", &N, &S, &T );
	
	for ( int i = 1; i <= N; ++i ){
		fscanf ( f, "%d%d", &a[i], &b[i] );
		
		while ( !Q.empty() && a[i] <= S * (i - Q.back()) + a[Q.back()] )
			Q.pop_back();
		
		Q.push_back ( i );
		
		total += 1LL* a[Q.front()]*b[i] + 1LL* S * ( i-Q.front() ) * b[i];
		
		if ( Q.front() == i - T )
			Q.pop_front();
		
	}
	
	fprintf ( g, "%lld", total );
	
	return 0;
}