CF1741E - Sending a Sequence Over the Network

https://codeforces.com/contest/1741/problem/E
Let's introduce the dynamics. \({\displaystyle dp[i]=true}\) if on the prefix ii the answer is Yes.

Then in this sequence \(b\) the numbers corresponding to the sizes of the segments from the partition \(a\) into subsegments will be called interesting.

A number at position \(i\) in the sequence \(b\), if it is interesting, is either to the right or to the left of the segment.

• If it is to the left of the segment, it can only be interesting if \(dp[i−1]=true\). Then \(dp[i+b[i]]=true.\)
• If it is on the right side of the segment, then if $ dp[i−b[i]−1]=true$, then \(dp[i]=true.\)

The answer for the whole sequence is Yes if $ dp[n]=true$.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll, i64;

void slv() {
    int n;
    cin >> n;
    vector<int> b(n + 1), dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        if (dp[i - 1] == 1 && i + b[i] <= n) {
            dp[i + b[i]] = 1;
        }
        if (i - b[i] - 1 >= 0 && dp[i - b[i] - 1]) {
            dp[i] = 1;
        }
    }
    cout << (dp[n] == 1 ? "yes" : "no") << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        slv();
    }
    return 0;
}