Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- By: facug91
- From:
- Name:
- Date: 28/09/2015
- */
- #include <bits/stdc++.h>
- #define next asjkdbg1238dv8ydf38gy832gf8yd
- #define prev asjkdbuiqdg783gdiu3dg79832dui
- #define EPS 1e-9
- #define MP make_pair
- #define DB(x) cerr << "#" << (#x) << ": " << (x) << " "
- #define DBL(x) cerr << "#" << (#x) << ": " << (x) << endl
- const double PI = 2.0*acos(0.0);
- #define INF 1000000000
- #define MINUSINF -10000000000000ll// -10^13
- #define MOD 1000000007ll
- //#define MAXN 10000100
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> ii; typedef pair<int, ii> iii;
- typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii;
- ll n, m, len, DP[105][1005], acc[100005], big[100005];
- int main () {
- ios_base::sync_with_stdio(0); cin.tie(0);
- //cout<<fixed<<setprecision(7); cerr<<fixed<<setprecision(7); //cin.ignore(INT_MAX, ' '); //cout << setfill('0') << setw(5) << 25
- int i, j, k;
- cin>>n>>m;
- memset(DP, 0, sizeof DP);
- for (i=1; i<=n; i++) {
- cin>>len;
- acc[0] = 0;
- for (j=1; j<=len; j++) {
- cin>>acc[j];
- acc[j] += acc[j-1];
- }
- big[0] = 0;
- for (j=1; j<=min(len, m); j++) {
- big[j] = 0;
- for (k=j; k<=len; k++) {
- big[j] = max(big[j], acc[k]-acc[k-j]);
- }
- //cerr<<"i "<<i<<" big["<<j<<"] "<<big[j]<<endl;
- }
- for (j=1; j<=m; j++) {
- for (k=0; k<=len; k++) {
- if (j-k < 0) DP[i][j] = max(DP[i][j], DP[i-1][j]);
- else DP[i][j] = max(DP[i][j], max(DP[i-1][j], DP[i-1][j-k]+big[k]));
- }
- }
- }
- cout<<DP[n][m]<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement