*TRT - Treats for the Cows

TRT - Treats for the Cows

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons:

• The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.
• Like fine wines and delicious cheeses, the treats improve with age and command greater prices.
• The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).
• Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.

Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?

The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains the value of treat v(i)

Output

The maximum revenue FJ can achieve by selling the treats

Example

Input:
5
1
3
1
5
2

Output:
43

-------------------------------------editorial---------------------------------------------------------

similar than optimal game stratgy but only difference is that player is only one , so and he has choice to chose either left or right at any instant

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a)  scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod  1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a);
#define pl(a) printf("%lld\n",a);
#define pi(a) printf("%d\n",a);
#define pd(a) printf("%lf\n",a);
#define pf(a) printf("%f\n",a);
lli  dp[3000][3000];
int solve(lli  arr[],int start,int end,int day)
 {


   if(start>end)return 0;
  
  if(start==end)
   {
  
       return day*dp[start][start];
    
   }
  else  if(dp[start][end]!=-1)
  {
 
   return dp[start][end];
   }
   
   
    else
    {
     
     lli val1=day*arr[start]+solve(arr,start+1,end,day+1);
      lli  val2=day*arr[end]+solve(arr,start,end-1,day+1);

      dp[start][end]=max(val1,val2);
    }
 return dp[start][end];
 }
int main()
{

int n;
lli arr[10000];
int t=1;
//while(1)
 {
    cin>>n;
   
    
    
    
      for(int i=0;i<n;i++)
   {
    cin>>arr[i];
      
   }
  
  for(int i=0;i<n;i++)
   {
     for(int j=0;j<n;j++)
     dp[i][j]=-1;
   }
   
  for(int i=0;i<n;i++) dp[i][i]=arr[i];
  
 solve(arr,0,n-1,1);
 
 
  cout<<dp[0][n-1]<<endl;
  } 
}