問題概要

マス目に $1, 2, \dots, N$ と記された $N$ マスの双六がある。1 からスタートして $N$ へ進みたい。

マス $i$ からマス $A_{i}$ ( $\gt i$ ) に進むことができて：100pt 獲得
マス $i$ からマス $B_{i}$ ( $\gt i$ ) に進むことができて：150pt 獲得

最大スコアを求めよ。

制約

$2 \le N \le 10^{5}$

コード

#include <bits/stdc++.h>
using namespace std;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
const int INF = 1 << 29;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 1; i < N; i++) cin >> A[i];
    for (int i = 1; i < N; i++) cin >> B[i];

    vector<int> dp(N+1, -INF);
    dp[1] = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] <= N) chmax(dp[A[i]], dp[i] + 100);
        if (B[i] <= N) chmax(dp[B[i]], dp[i] + 150);
    }
    cout << dp[N] << endl;
}