15486 ํ‡ด์‚ฌ2

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
int N, T[1500000], P[1500000], DP[1500000];
 
int dp(int deep);
int max(int a, int b) {
	return a > b ? a : b;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
 
	for (int i = 0; i < N; i++) {
		cin >> T[i] >> P[i];
	}
 
	cout << dp(0);
}
 
int dp(int deep) {
	if (deep >= N)
		return 0;
	if (DP[deep] != 0)
		return DP[deep];
 
	int result = 0;
	if (deep + T[deep] <= N)
		result = dp(deep + T[deep]) + P[deep];
	result = max(result, dp(deep + 1));
 
	return DP[deep] = result;
}