Cod sursa(job #3359181)

Utilizator cristian46290Petre Cristian cristian46290 Data 25 iunie 2026 20:29:57
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;
typedef long long int ll;

const int nMax = 2e5 + 5;

int T, n;
int a[nMax], dp[nMax];

void solve()
{
    int rez = 0;
    dp[0] = 0,dp[1] = 0;
    for (int i = 1;i <= n;i++){
        if (i + a[i] > n){rez = max(rez,dp[i]+a[i]);continue;}
        dp[i+a[i]] = max(dp[i+a[i]],dp[i]+a[i]);
    }
    cout << rez << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--){
        cin >> n;
        for (int i = 1;i <= n;i++)cin >> a[i],dp[i] = 0;
        solve();
    }
}