fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pb push_back
  5. #define sz(a) a.size()
  6. #define endl '\n'
  7. #define inf int(1e9)
  8. #define mod 1000000007
  9. #define fastio std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  10. #define rep(i,a,b) for( int i=a; i<b; i++)
  11. #define ii pair < ll , ll >
  12. #define F first
  13. #define S second
  14. #define input freopen("C:\\Users\\ASUS\\Desktop\\input.txt","r+",stdin)
  15. #define output freopen("C:\\Users\\ASUS\\Desktop\\output.txt","w+",stdout)
  16. #define debug input; output
  17.  
  18. using namespace std;
  19.  
  20.   const int N=1003;
  21.   string v[N];
  22.   ll t[N];
  23.   ll vis[N];
  24. ll dp[N][N];
  25.   ll solve(int a, int b)
  26.     {
  27.       if (a>b)
  28.          return 0;
  29.          if( dp[a][b]==-1)
  30.       dp[a][b]=  max(t[a] + min(solve(a+2,b),solve(a+1,b-1)) , t[b]+min(solve(a,b-2),solve(a+1,b-1)) );
  31.       return dp[a][b];
  32.     }
  33.  
  34.   int main()
  35.     { fastio;
  36.  
  37.       int tc;
  38.       cin>>tc;
  39.       while(tc--){
  40.           memset(dp,-1,sizeof(dp));
  41.         int n;
  42.         cin>>n;
  43.         ll sum=0;
  44.         for(int i=1;i<=n;i++){
  45.            cin>>t[i];
  46.            sum+=t[i];
  47.         }
  48.  
  49.         ll ans=solve(1,n);
  50.         cout<<(ans-(sum-ans))<<endl;
  51.       }
  52.     }
Time limit exceeded #stdin #stdout 5s 23544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k7RJlM
language:
C++ (gcc 8.3)
created:
7 years 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!