Problemas da Semana Noic - Avançado Semana 2

passaros.cpp

// Problemas da Semana Noic - Avançado Semana 2
// Pássaros - Complexidade O(c * sum(c_i))

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e3+10;
const int maxc = 2e4+10;
const ll inf = 1e18; // valor "infinito" (muito grande)
 
ll dp[maxn][maxc];
 
int c[maxn];
int cost[maxn];
 
int main(void)
{
	int n, W, B, X;
	scanf("%d %d %d %d", &n, &W, &B, &X);
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &c[i]);
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &cost[i]);

	// inicializamos dp com valores muito pequenos
	for (int i = 0; i <= n; i++)
		for (int j = 0; j < maxc; j++)
			dp[i][j] = -inf;

	// caso base (antes de chegar na árvore 1, com 0 pássaros)
	dp[0][0] = W;
 	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= 10000; j++)
		{
			for (int k = 0; k <= c[i]; k++)
			{
				// só podemos usar k pássaros se não ultrapassarmos a quantidade de magia atual
				if (dp[i-1][j] - 1ll*k*cost[i] >= 0)
				{
					ll cap = 1ll*B*(j+k) + 1ll*W;

					dp[i][j+k] = max(dp[i][j+k], min(cap, dp[i-1][j] + 1ll*X - 1ll*cost[i]*k));
				}
			}
		}
	}
 	
 	// encontramos a maior quantidade possível de pássaros
	for (int j = 10000; j >= 0; j--)
	{
		if (dp[n][j] >= 0)
		{
			printf("%d\n", j);
			return 0;
		}
	}
}