Cod sursa(job #822885)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 24 noiembrie 2012 10:18:03
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <stdlib.h>
#include <algorithm>
#include <deque>
using namespace std;

ifstream fi ("branza.in");
ofstream fo ("branza.out");

const int dim = 100005; 
int N, S, T, P[dim], C[dim];
long long D1, D2;
deque <int> Q;

void cit ()
{
	fi >> N >> S >> T;
	for (int i = 1; i <= N; i++)
	{
		fi >> C[i] >> P[i];		
	}	
}

inline int cost (int i ,int j)
{
	return C[j] + (i - j) * S;
}

void rez ()
{
	int i;
	D1 = D2 = 0;
	for (i = 1; i <= N; i++)
	{
		while (!Q.empty() && cost(i, Q.back()) >= C[i])
			Q.pop_back ();
		Q.push_back (i);
		if (i - Q.front() == T + 1)
			Q.pop_front ();
		D1 = D2 + (long long)P[i] * cost (i, Q.front());
		D2 = D1;
	}
}

void rezbrut ()
{
	int i, j, m;
	D1 = D2 = 0;
	for (i = 1; i <= N; i++)
	{
		m = C[i];
		for (j = 1; j <= T && i-j > 0; j++)
		{
			m = min (m, C[i-j] + j*S);
		}
		D1 = D2 + (long long)P[i] * m;
		D2 = D1;
	}	
}

void afi ()
{
	fo << D1 << '\n';
}

int main ()
{
	cit ();
	
	rez ();
	afi ();
	
	/*
	rezbrut ();
	afi ();
	*/
	return 0;
}