Noic - Semana 64 - Avançado

noic-s64-avancado.cpp

// Noic - Semana 64 - Avançado
// Complexidade: O(n)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef long long ll;

int d[maxn], w[maxn];

ll dp[maxn][2];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> d[i] >> w[i];

	// casos base
	dp[1][0] = d[1], dp[1][1] = max(0, d[1]-w[2]);

	for (int i = 2; i <= n; i++)
	{
		// possibilidades para dp[i][0]
		ll b1 = 1LL*d[i] + dp[i-1][1];
		ll b2 = dp[i-1][0] + 1LL*max(0, d[i]-w[i-1]);

		dp[i][0] = min(b1, b2);

		// perceba que se i = n, não há pilar i+1
		if (i < n)
		{
			// possibilidades para dp[i][1]
			ll c1 = 1LL*max(0, d[i]-w[i+1]) + dp[i-1][1];
			ll c2 = dp[i-1][0] + 1LL*max(0, d[i]-w[i-1]-w[i+1]);

			dp[i][1] = min(c1, c2);
		}
	}

	// resposta do problema
	cout << dp[n][0] << "\n";
}