fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 3002;
  4. int dp[N][N], a[N], n;
  5.  
  6. int main(int argc, char const *argv[])
  7. {
  8.   scanf("%d", &n);
  9.   for (int i = 0; i < n; ++i)
  10.   {
  11.     scanf("%d", a+i);
  12.     dp[0][i] = 1;
  13.   }
  14.   for (int i = 1; i < n; ++i)
  15.   {
  16.     int sum_cur = 0;
  17.     int sum_prev = 0;
  18.     int x = i;
  19.     int dpp = 0;
  20.     for (int j = i; j < n; ++j)
  21.     {
  22.       sum_cur += a[j];
  23.  
  24.       dp[i][j] = dpp;
  25.       while (x)    // monotonic property 
  26.       {
  27.         if (sum_prev + a[x - 1] > sum_cur) break;
  28.         sum_prev += a[--x];
  29.         dp[i][j] = max(dp[x][i-1] + 1, dp[i][j]);
  30.       }
  31.       dpp = dp[i][j];
  32.     }
  33.   }
  34.  
  35.   // for (int i = 0; i < n; ++i) {
  36.   //   for (int j = 0; j < n; ++j)
  37.   //     printf("%d ", dp[i][j]);
  38.   //   puts("");
  39.   // }
  40.  
  41.   int ans = 0;
  42.   for (int i = 0; i < n; ++i)
  43.     ans = max(ans, dp[i][n-1]);
  44.   printf("%d\n", ans);
  45.  
  46.   return 0;
  47. }
Success #stdin #stdout 0s 38680KB
comments (?)
stdin
copy 
6
6 4 2 2 2 2
stdout
copy 
3
https://ideone.com/OdxY57
language:
C++14 (gcc 8.3)
created:
9 years 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!