알고리즘

BOJ 15486: 퇴사 2

minbear 2023. 5. 19. 02:02

#BOJ 15486: 퇴사 2

 

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

#코드

#include<iostream> //#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n;
int t[1500001];
int p[1500001];
int d[1500001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}

	for (int i = 1; i <= n; i++) {
		d[i] = max(d[i], d[i - 1]);

		if (i + t[i] - 1 <= n)
		{
			d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]);
		}
	}
	cout << max(d[n], d[n + 1]);
	return 0;
}