Cod sursa(job #1392848)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 martie 2015 22:18:18
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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, p, u;
long long d[NMax];

struct mdeque
{
	int pos;
	int val;
}deq[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;

	}*/

	deq[p].val = b[1].c - s;
	for (int i = 1; i <= n; i++) {

		while (i - deq[p].pos > t && p <= u)
			p++;
		d[i] = getmin(b[i].c, deq[p].val + i * s);
		d[i] *= b[i].p;
		d[i] += d[i - 1];
		long long cost = b[i].c - i * s;

		while (deq[u].val >= cost && p <= u)
			u--;
		deq[++u].pos = i;
		deq[u].val = cost;
	}

	g << d[n];
}