Cod sursa(job #1392743)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 martie 2015 21:04:19
Problema Branza Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

#define NMax 100010
#define INF (1<<31)-1;

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int n, s, t;
long long d[NMax];
struct branza
{
	int c;
	int p;
}b[NMax];

int getmin(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

int getmax(int a, int b)
{
	if (a > b)
		return a;
	return b;
}

int main()
{
	f >> n >> s >> t;
	for (int i = 1; i <= n; i++)
		f >> b[i].c >> b[i].p;

	for (int i = 1; i <= n; i++) {
		d[i] = d[i - 1];
		long long cmin = INF;
		for (int sapt = i; sapt >= getmax(1, i - t); sapt--)
			cmin = getmin(cmin, 1LL * b[sapt].c + (i - sapt)*s);
		d[i] += cmin * b[i].p;
	}
	g << d[n];
}