A good question of knapsack approach.We will first fill the table of dp[n+1][m+1] where dp[i][j]=maximum value of sub-array of size j we can get from the ith block.Then we have to maximize the total value in the box such that we choose only one sub-array from each block and the total sum of lengths of sub-arrays is less than m.
So for this we will change definition of dp[i][j] as maximum value we get for box of length j by choosing subarrays from only first i blocks(knapsack 0/1).
dp[i][j] =max( dp[i-1][j-k]+ dp[i][k] ) for 0<=k<=j
Remember to pad appropriately while using prefix sums and maintaining the dp array also update dp[i][j] in above step in a temporary array and then copy it into dp[i][j].
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v) \
cout << endl; \
rep(i, 0, v.size()) cout << v[i] << " "; \
cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))
ll mod(ll n){
return n%(ll)mo;
}
int main(){fastio
ll n,m;cin>>n>>m;
ll dp[n+1][m+1];
memset( dp,0,sizeof(dp) );
vector < mv > v;
rep(i,0,n){
mv g;
ll k;cin>>k; g.pb(0);
rep(i,0,k){
ll p;cin>>p;g.pb(p);
}
rep(i,1,k+1)g[i]+=g[ i-1 ];
v.pb(g);
}
rep(i,1,n+1){
rep(j,1, m+1){
ll mx=0, s=v[i-1].size() ;
rep(u,j, s)mx=max(mx, v[i-1][u]- v[i-1][u-j] );
if(s-1 < j)dp[i][j]=dp[i][j-1];
else dp[i][j]=mx;
}
}
rep(i,1,n+1){ ll dm[m+1];dm[0]=0;
rep(j,1,m+1){
ll mx=-inf;
rep(k,0,j+1){
mx=max(mx, dp[i-1][j-k] + dp[i][k] );
}
dm[j]=mx;
}
rep(j,0,m+1)dp[i][j]=dm[j];
}
cout<<dp[n][m]<<endl;
}
achieveit 