Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <unordered_map>
- #include <vector>
- using namespace std;
- #define ull unsigned long long
- unordered_map<string, ull> cache;
- ull dp(const vector<ull>& prefix, ull l, ull r) {
- if (l >= r) {
- return 0;
- }
- string key = l + "-" + r;
- if (cache.find(key) != cache.end()) {
- return cache[key];
- }
- ull current = 0;
- for (ull i = l; i < r; ++i) {
- ull scoreL = prefix[i];
- if (l > 0) {
- scoreL -= prefix[l - 1];
- }
- ull scoreR = prefix[r] - prefix[i];
- if (scoreL > scoreR) {
- current = max(current, scoreR + dp(prefix, i + 1, r));
- } else if (scoreL < scoreR) {
- current = max(current, scoreL + dp(prefix, l, i));
- } else {
- ull tempL = scoreL + dp(prefix, i + 1, r);
- ull tempR = scoreR + dp(prefix, l, i);
- current = max(current, max(tempL, tempR));
- }
- }
- cache[key] = current;
- return current;
- }
- int main() {
- ull n;
- cin >> n;
- vector<ull> N(n);
- for (ull i = 0; i < n; ++i) {
- cin >> N[i];
- }
- vector<ull> prefix(N.size());
- prefix[0] = N[0];
- for (size_t i = 1; i < N.size(); ++i) {
- prefix[i] = N[i] + prefix[i - 1];
- }
- cout << dp(prefix, 0, prefix.size() - 1) << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement