• API
• FAQ
• Tools
• Archive
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.
Top