fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define maxn 2005
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. int n;
  10. int a[maxn], pref[maxn];
  11. int val[maxn][maxn];
  12. int opt[maxn][maxn];
  13.  
  14. inline int get(int l, int r){
  15.     return pref[r] - pref[l-1];
  16. }
  17.  
  18. void solve(int l, int r, int optl, int optr){
  19.     if(l > r) return;
  20.     int mid = (l + r) >> 1;
  21.  
  22.     int best = -1;
  23.     int best_k = -1;
  24.  
  25.     for(int k = optl; k <= min(mid-1, optr); k++){
  26.         int cur = min(val[1][k], val[k+1][mid]);
  27.         if(cur > best){
  28.             best = cur;
  29.             best_k = k;
  30.         }
  31.     }
  32.  
  33.     val[1][mid] = get(1, mid) + best;
  34.     opt[1][mid] = best_k;
  35.  
  36.     solve(l, mid-1, optl, best_k);
  37.     solve(mid+1, r, best_k, optr);
  38. }
  39.  
  40. signed main(){
  41.     itachi
  42.  
  43.     cin >> n;
  44.     for(int i = 1; i <= n; i++){
  45.         cin >> a[i];
  46.         pref[i] = pref[i-1] + a[i];
  47.         val[i][i] = a[i];
  48.         opt[i][i] = i;
  49.     }
  50.  
  51.     for(int len = 2; len <= n; len++){
  52.         for(int l = n-len+1; l >= 1; l--){
  53.             int r = l + len - 1;
  54.  
  55.             int L = opt[l][r-1];
  56.             int R = opt[l+1][r];
  57.  
  58.             int best = -1;
  59.             int best_k = -1;
  60.  
  61.             for(int k = L; k <= R; k++){
  62.                 int cur = min(val[l][k], val[k+1][r]);
  63.                 if(cur > best){
  64.                     best = cur;
  65.                     best_k = k;
  66.                 }
  67.             }
  68.  
  69.             val[l][r] = get(l, r) + best;
  70.             opt[l][r] = best_k;
  71.         }
  72.     }
  73.  
  74.     cout << val[1][n] - get(1, n);
  75. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zYmFkN
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!