fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 2005;
  9.  
  10. int n;
  11. int a[MAXN];
  12. int pref[MAXN];
  13. int val[MAXN][MAXN];
  14.  
  15. inline int getSum(int l, int r){
  16.     return pref[r] - pref[l - 1];
  17. }
  18.  
  19. signed main() {
  20.     itachi
  21.  
  22.     cin >> n;
  23.     for(int i = 1; i <= n; i++){
  24.         cin >> a[i];
  25.         pref[i] = pref[i - 1] + a[i];
  26.         val[i][i] = a[i];
  27.     }
  28.  
  29.     for(int len = 2; len <= n; len++){
  30.         for(int l = 1; l + len - 1 <= n; l++){
  31.             int r = l + len - 1;
  32.  
  33.             int lo = l, hi = r - 1;
  34.             while(lo < hi){
  35.                 int mid = (lo + hi) >> 1;
  36.                 if(val[l][mid] < val[mid + 1][r]) lo = mid + 1;
  37.                 else hi = mid;
  38.             }
  39.  
  40.             int best = -1;
  41.             for(int m = max(l, lo - 1); m <= min(r - 1, lo); m++){
  42.                 best = max(best, min(val[l][m], val[m + 1][r]));
  43.             }
  44.  
  45.             val[l][r] = getSum(l, r) + best;
  46.         }
  47.     }
  48.  
  49.     cout << val[1][n] - getSum(1, n) << '\n';
  50.     return 0;
  51. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/tinGoL
language:
C++14 (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!