fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(ll i = (a);i <= (b);i++)
  3. #define FOD(i,a,b) for(ll i = (a);i >= (b);i--)
  4. #define ft first
  5. #define sc second
  6. #define el "\n"
  7. #define vector2 vector<vector<ll>>
  8. using namespace std;
  9.  
  10. using ll = long long;
  11. using ldb = long double;
  12. using pii = pair<int,int>;
  13. using pll = pair<ll,ll>;
  14. const ll MOD = 1e9 + 7;
  15. const ll MAX = 1e18;
  16. const ll mma = 6e6+100;
  17. const ll mod = 998244353;
  18. const ll testcase = 1e3;
  19. const ll mang = 1e5 + 100;
  20. ll n,m,q,k;
  21. vector<ll> a(5005);
  22. ll dp[5005][5005];
  23. int main(){
  24.     #define TASK "KEOCO"
  25.  
  26.     cin.tie(0) -> sync_with_stdio(0);
  27.     //freopen(TASK".inp", "r", stdin);
  28.     //freopen(TASK".out", "w",  stdout);
  29.     cin >> n;
  30.     ll cnt = 0;
  31.     FOR(i,1,n){
  32.         cin >> a[i];
  33.         dp[i][i] = a[i];
  34.         cnt += a[i];
  35.     }
  36.  
  37.     FOR(len,2,n){
  38.         for(ll l = 1;l + len - 1 <= n;l++){
  39.             ll r = l + len - 1;
  40.             dp[l][r] = max(-dp[l + 1][r] + a[l],-dp[l][r - 1] + a[r]);
  41.         }
  42.     }
  43.     cout << (cnt + dp[1][n]) / 2;
  44. }
  45.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6haCOn
language:
C++14 (gcc 8.3)
created:
7 hours 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!