fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<int> riceBalls;
  7. vector<int> prefixSum;
  8. vector<vector<int>> memo;
  9.  
  10. // Helper function to calculate sum of rice balls from index i to j
  11. int getSum(int i, int j) {
  12.     return prefixSum[j + 1] - prefixSum[i];
  13. }
  14.  
  15. // Recursive function to find the maximum rice ball size that can be formed from subarray [i, j]
  16. int maxRiceBall(int i, int j) {
  17.     if (i == j) return riceBalls[i]; // Single rice ball case
  18.     if (memo[i][j] != -1) return memo[i][j]; // Return memoized result if available
  19.  
  20.     int maxBall = 0;
  21.  
  22.     // Try merging adjacent sections
  23.     for (int mid = i; mid < j; ++mid) {
  24.         if (maxRiceBall(i, mid) == maxRiceBall(mid + 1, j)) {
  25.             maxBall = max(maxBall, maxRiceBall(i, mid) + maxRiceBall(mid + 1, j));
  26.         }
  27.     }
  28.  
  29.     // Try merging with one rice ball in between
  30.     for (int mid = i; mid < j - 1; ++mid) {
  31.         int leftSum = getSum(i, mid);
  32.         int rightSum = getSum(mid + 2, j);
  33.  
  34.         if (leftSum == rightSum) {
  35.             int leftMax = maxRiceBall(i, mid);
  36.             int rightMax = maxRiceBall(mid + 2, j);
  37.             if (leftMax > 0 && rightMax > 0) {
  38.                 maxBall = max(maxBall, leftSum + riceBalls[mid + 1] + rightSum);
  39.             }
  40.         }
  41.     }
  42.  
  43.     // Store and return the maximum size for the subarray [i, j]
  44.     memo[i][j] = max(maxBall, getSum(i, j)); // Consider the option of not merging at all
  45.     return memo[i][j];
  46. }
  47.  
  48. int main() {
  49.     int N;
  50.     cin >> N;
  51.     riceBalls.resize(N);
  52.     prefixSum.resize(N + 1, 0);
  53.     memo.assign(N, vector<int>(N, -1));
  54.  
  55.     for (int i = 0; i < N; ++i) {
  56.         cin >> riceBalls[i];
  57.         prefixSum[i + 1] = prefixSum[i] + riceBalls[i];
  58.     }
  59.  
  60.     // Calculate the largest rice ball possible
  61.     int maxRiceBallSize = 0;
  62.     for (int i = 0; i < N; ++i) {
  63.         for (int j = i; j < N; ++j) {
  64.             maxRiceBallSize = max(maxRiceBallSize, maxRiceBall(i, j));
  65.         }
  66.     }
  67.  
  68.     cout << maxRiceBallSize << endl;
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
7
47 12 12 3 9 9 3
stdout
copy 
95
https://ideone.com/fp1KB5
language:
C++14 (clang 8.0)
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!