Problem 67

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int t;
long arr[5051];
bool flag[5051];

long sum(int i,int step)
{
if(i>5050)
return 0;

if(flag[i] == true)
return arr[i];

//cout<<i<<" "<<arr[i]<<endl;

long left = sum(i+step, step+1);
long right = sum(i+step+1, step+1);

arr[i] += max(left, right);
//cout<<i<<" "<<arr[i]<<endl;
flag[i] = true;
return arr[i];
}

int main()
{

freopen("in.txt","r",stdin);

memset(flag, 0, sizeof(flag));

int a, i=1;
t=1;
while(cin>>a)
{
arr[i] = a;
i++;
}

cout<<sum(1,1)<<endl;


//cout<<in<<endl;

return 0;
}