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, elem, sum, tail, ans, DP[105][1005];
- vector<ll> block[105], opt[105];
- ll dp (int idx, int res) {
- if (idx == n) return 0ll;
- if (DP[idx][res] != -1) return DP[idx][res];
- ll ans = 0ll;
- for (int i=0; i<=min(res, (int)block[idx].size()); i++) {
- ans = max(ans, dp(idx+1, res-i) + opt[idx][i]);
- }
- return DP[idx][res] = ans;
- }
- 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;
- for (i=0; i<n; i++) {
- cin>>len;
- block[i].push_back(0);
- for (j=1; j<=len; j++) {
- cin>>elem;
- block[i].push_back(elem);
- block[i][j] += block[i][j-1];
- }
- opt[i].push_back(0);
- for (j=1; j<=min(len, m); j++) {
- ans = 0;
- for (k=j; k<=len; k++) ans = max(ans, block[i][k]-block[i][k-j]);
- opt[i].push_back(ans);
- }
- }
- memset(DP, -1, sizeof DP);
- cout<<dp(0, m)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement