G2A Many GEOs
SHARE
TWEET

CUBE Task_00025 28/3/63

mickypinata Mar 28th, 2020 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. typedef long long lli;
  5.  
  6. vector<int> qsum;
  7. int n;
  8.  
  9. vector<vector<lli>> memo;
  10. lli Separate(int s, int e){
  11.     if(memo[s][e] != -1){
  12.         return memo[s][e];
  13.     }
  14.     if(s == e){
  15.         return memo[s][e] = 0;
  16.     } else {
  17.         int x1, x2;
  18.         lli mx = 0;
  19.         for(int i = s; i < e; ++i){
  20.             x1 = qsum[i] - qsum[s - 1];
  21.             x2 = qsum[e] - qsum[i];
  22.             mx = max(mx, 2 * min(x1, x2) + max(x1, x2) + Separate(s, i) + Separate(i + 1, e));
  23.         }
  24.         return memo[s][e] = mx;
  25.     }
  26. }
  27.  
  28. void PrintQSum(){
  29.     for(int i = 1; i <= n; ++i){
  30.         cout << qsum[i] << " ";
  31.     }
  32.     cout << "\n";
  33.     return;
  34. }
  35.  
  36. int main(){
  37.  
  38.     int x;
  39.  
  40.     scanf("%d", &n);
  41.     qsum.assign(n + 1, 0);
  42.     for(int i = 1; i <= n; ++i){
  43.         scanf("%d", &x);
  44.         qsum[i] = qsum[i - 1] + x;
  45.     }
  46.  
  47.     memo.assign(n + 1, vector<lli>(n + 1, -1));
  48.     cout << Separate(1, n);
  49.  
  50.     return 0;
  51. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top