Advertisement
facug91

Untitled

Oct 6th, 2015
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 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, DP[105][1005], acc[100005], big[100005];
  28.  
  29. int main () {
  30.     ios_base::sync_with_stdio(0); cin.tie(0);
  31.     //cout<<fixed<<setprecision(7); cerr<<fixed<<setprecision(7); //cin.ignore(INT_MAX, ' '); //cout << setfill('0') << setw(5) << 25
  32.     int i, j, k;
  33.    
  34.     cin>>n>>m;
  35.     memset(DP, 0, sizeof DP);
  36.     for (i=1; i<=n; i++) {
  37.         cin>>len;
  38.         acc[0] = 0;
  39.         for (j=1; j<=len; j++) {
  40.             cin>>acc[j];
  41.             acc[j] += acc[j-1];
  42.         }
  43.         big[0] = 0;
  44.         for (j=1; j<=min(len, m); j++) {
  45.             big[j] = 0;
  46.             for (k=j; k<=len; k++) {
  47.                 big[j] = max(big[j], acc[k]-acc[k-j]);
  48.             }
  49.             //cerr<<"i "<<i<<" big["<<j<<"] "<<big[j]<<endl;
  50.         }
  51.         for (j=1; j<=m; j++) {
  52.             for (k=0; k<=len; k++) {
  53.                 if (j-k < 0) DP[i][j] = max(DP[i][j], DP[i-1][j]);
  54.                 else DP[i][j] = max(DP[i][j], max(DP[i-1][j], DP[i-1][j-k]+big[k]));
  55.             }
  56.         }
  57.     }
  58.     cout<<DP[n][m]<<endl;
  59.    
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement