fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3. typedef long long ll; 
  4.  
  5. using namespace std;
  6. const int N = 3e3 + 5; 
  7. struct info{
  8.      ll x; 
  9.      ll y; 
  10. }; 
  11. info dp[N][N][2]; 
  12. bool vis[N][N][2]; 
  13.  
  14. int n; 
  15. vector<ll>a; 
  16. info solve(int l, int r, int t){
  17. 	info val; val.x = 0; val.y = 0; 
  18. 	if(l > r) return val; 
  19. 	if(vis[l][r][t]) return dp[l][r][t]; 
  20.     vis[l][r][t] = 1; 
  21.  
  22. 	if(t == 0){
  23.         info op1; 
  24.         info res = solve(l,r-1,1); 
  25.         op1.x = a[r] + res.x; 
  26.         op1.y = res.y; 
  27.         info op2; 
  28.         info res2 = solve(l+1,r,1); 
  29.         op2.x = a[l] + res2.x; op2.y = res2.y; 
  30.         ll op1dif = op1.x - op1.y; 
  31.         ll op2dif = op2.x - op2.y; 
  32.         if(op1dif >= op2dif) return dp[l][r][t] = op1; 
  33.         else return dp[l][r][t] = op2; 
  34.     }
  35.     else {
  36.         info op1; 
  37.         info res = solve(l,r-1,0); 
  38.         op1.y = a[r] + res.y; 
  39.         op1.x = res.x; 
  40.         info op2; 
  41.         info res2 = solve(l+1,r,0); 
  42.         op2.y = a[l] + res2.y; op2.x = res2.x; 
  43.         ll op1dif = op1.x - op1.y; 
  44.         ll op2dif = op2.x - op2.y; 
  45.         if(op1dif <= op2dif) return dp[l][r][t] = op1; 
  46.         else return dp[l][r][t] = op2; 
  47.     }
  48. }
  49. int main() {
  50. 	ios_base::sync_with_stdio(false); 
  51.     cin.tie(NULL); cout.tie(NULL); 
  52.     memset(dp, -1, sizeof(dp)); 
  53.     cin>>n; 
  54.     a.resize(n); 
  55.     for(int i = 0; i < n; i++) cin>>a[i]; 
  56.     info ans = solve(0,n - 1, 0); 
  57.     cout<<ans.x - ans.y<<endl; 
  58. }
Success #stdin #stdout 0.04s 286352KB
comments (?)
stdin
copy 
6
4 2 9 7 1 5
stdout
copy 
2
https://ideone.com/ioT1Vf
language:
C++ (gcc 8.3)
created:
4 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!