题解 | #小美和大富翁#

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef pair<int,int>PII;
typedef pair<int,__int128>PI;
typedef pair<double,double>PDD;
typedef pair<LL,LL>PLL;
typedef tuple<LL,LL,LL,LL>t4i;
typedef tuple<int,int,int>t3i;
const long double eps=1e-7;
const int inf=0x3f3f3f3f;
const long long INF=1e18;
const double pai=acos(-1.0);
const int mod=1e9+7;
const int N=1e5+10,M=2e6+10;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//__builtin_popcountll(x)
LL dp[N],a[N];
int p[5];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],dp[i]=-INF;
	dp[0]=0;
	queue<PLL>q;
	q.push({0,0});
	while(q.size()){
		auto [ps,nw]=q.front();q.pop();
		if(nw<dp[ps]) continue;
		for(int i=1;i<=4;i++) p[i]=i;
		do{
			LL pos=ps,now=nw;
			bool ok=true;
			for(int i=1;i<=4;i++){
				LL x=pos+p[i];
				if(x<=n&&now+a[x]>=0) dp[x]=max(dp[x],now+a[x]),pos=x,now+=a[x];
				else{
					ok=false;
					break;
				}
			}
			if(ok) q.push({pos,now});
		}while(next_permutation(p+1,p+5));
	}
	if(dp[n]>=0) printf("%lld\n",dp[n]);
	else printf("-1\n");
}
int main()
{
	ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    int tt;tt=1;
   	//cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}