fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. #define inf 1e9
  10. #define MOD 1000000007
  11. vector<vector < ll > > dp( 5001, vector<ll>(5001, -1));
  12. vector  < ll > a ;
  13.  ll n , sum  = 0 ;
  14. ll find_max(ll left   , ll right , int player  ) {
  15.     if (left ==  right ) {
  16.         if (player == 0 ) return a[left] ;
  17.         else return  0 ;
  18.     }
  19.     ll &p = dp[left][right]  ;
  20.     if (p != -1 )return p   ;
  21.     if (player  == 0 ) return  p = max ( a[left] + find_max (left +1 , right , 1    ) , a[right]  + find_max( left , right -1 ,  1) );
  22.     return  p = min (  find_max (left +1 , right ,      0   ) ,   find_max( left , right -1 ,  0) );
  23.  
  24. }
  25. void solve() {
  26.     cin >> n ;
  27.     a.assign (n + 1   ,  0 ) ;
  28.     for (int i = 0 ; i < n ; i++) {
  29.         cin >> a[i] ;
  30.         sum+=a[i] ;
  31.     }
  32.     cout << find_max (0 , n-1  , 0 );
  33.  
  34.  
  35. }
  36.  
  37. int main() {
  38.     ios::sync_with_stdio(false);
  39.     cin.tie(0);
  40. #ifndef ONLINE_JUDGE
  41.     freopen("input.txt", "r", stdin);
  42.     freopen("output.txt", "w", stdout);
  43. #endif
  44.     ll t = 1;
  45.  
  46.     //cin >> t;
  47.     while (t--) {
  48.         solve();
  49.     }
  50.     return 0;
  51. }
Success #stdin #stdout 0.09s 199060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
40017
https://ideone.com/cxsL4w
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!