madhukeshk3

L-Dequeue Atcoder

Jul 31st, 2020 (edited)
317
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pfin(a) printf("%d\n",a);
  5. #define pfln(a) printf("%lld\n",a);
  6. #define pfis(a) printf("%d ",a);
  7. #define pfls(a) printf("%lld ",a);
  8. #define sfi(a) scanf("%d",&a);
  9. #define sfl(a) scanf("%lld",&a);
  10. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define pb(a) push_back(a);
  13. #define mp(a,b) make_pair(a,b)
  14. #define ll long long
  15.  
  16. const ll mod=1e9+7;
  17.  
  18. int main()
  19. {
  20.     int n;
  21.     sfi(n)
  22.  
  23.     ll arr[n+1];
  24.     f(i,1,n+1)
  25.         sfl(arr[i])
  26.  
  27.     ll dp[n+1][n+1];
  28.  
  29.     memset(dp,0,sizeof(dp));
  30.  
  31.     for(int i=n;i>0;i--)
  32.     {
  33.         f(j,i,n+1)
  34.         {
  35.             if(i==j)
  36.                 dp[i][j]=arr[i];
  37.             else
  38.             {
  39.                 dp[i][j]=max((arr[i]-dp[i+1][j]),(arr[j]-dp[i][j-1]));
  40.             }
  41.         }
  42.     }
  43.  
  44.     pfln(dp[1][n])
  45.  
  46.     return 0;
  47. }
RAW Paste Data