Advertisement
facug91

Untitled

Oct 5th, 2015
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. /*
  2.     By: facug91
  3.     From:
  4.     Name:
  5.     Date: 28/09/2015
  6. */
  7.  
  8. #include <bits/stdc++.h>
  9. #define next asjkdbg1238dv8ydf38gy832gf8yd
  10. #define prev asjkdbuiqdg783gdiu3dg79832dui
  11. #define EPS 1e-9
  12. #define MP make_pair
  13. #define DB(x) cerr << "#" << (#x) << ": " << (x) << " "
  14. #define DBL(x) cerr << "#" << (#x) << ": " << (x) << endl
  15. const double PI = 2.0*acos(0.0);
  16.  
  17. #define INF 1000000000
  18. #define MINUSINF -10000000000000ll// -10^13
  19. #define MOD 1000000007ll
  20. //#define MAXN 10000100
  21.  
  22. using namespace std;
  23. typedef long long ll;
  24. typedef pair<int, int> ii; typedef pair<int, ii> iii;
  25. typedef vector<int> vi; typedef vector<ii> vii;        typedef vector<iii> viii;
  26.  
  27. ll n, m, len, elem, sum, tail, ans, DP[105][1005];
  28. vector<ll> block[105], opt[105];
  29.  
  30. ll dp (int idx, int res) {
  31.     if (idx == n) return 0ll;
  32.     if (DP[idx][res] != -1) return DP[idx][res];
  33.     ll ans = 0ll;
  34.     for (int i=0; i<=min(res, (int)block[idx].size()); i++) {
  35.         ans = max(ans, dp(idx+1, res-i) + opt[idx][i]);
  36.     }
  37.     return DP[idx][res] = ans;
  38. }
  39.  
  40. int main () {
  41.     ios_base::sync_with_stdio(0); cin.tie(0);
  42.     //cout<<fixed<<setprecision(7); cerr<<fixed<<setprecision(7); //cin.ignore(INT_MAX, ' '); //cout << setfill('0') << setw(5) << 25
  43.     int i, j, k;
  44.    
  45.     cin>>n>>m;
  46.     for (i=0; i<n; i++) {
  47.         cin>>len;
  48.         block[i].push_back(0);
  49.         for (j=1; j<=len; j++) {
  50.             cin>>elem;
  51.             block[i].push_back(elem);
  52.             block[i][j] += block[i][j-1];
  53.         }
  54.         opt[i].push_back(0);
  55.         for (j=1; j<=min(len, m); j++) {
  56.             ans = 0;
  57.             for (k=j; k<=len; k++) ans = max(ans, block[i][k]-block[i][k-j]);
  58.             opt[i].push_back(ans);
  59.         }
  60.     }
  61.     memset(DP, -1, sizeof DP);
  62.     cout<<dp(0, m)<<endl;
  63.    
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement