fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll NEG_INF = -(ll)4e18;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, m;
  11.     cin >> n >> m;
  12.     vector<vector<ll>> v(n);
  13.     vector<int> sz(n);
  14.     for(int i = 0; i < n; i++){
  15.         cin >> sz[i];
  16.         v[i].resize(sz[i]);
  17.         for(int j = 0; j < sz[i]; j++){
  18.             cin >> v[i][j];
  19.         }
  20.     }
  21.  
  22.     // 1) For each shelf i, precompute best[i][k] = max sum by taking exactly k items from its two ends.
  23.     vector<vector<ll>> best(n, vector<ll>(m+1, NEG_INF));
  24.     for(int i = 0; i < n; i++){
  25.         int s = sz[i];
  26.         // prefix sums from left, suffix sums from right
  27.         vector<ll> pref(s+1, 0), suff(s+1, 0);
  28.         for(int j = 1; j <= s; j++){
  29.             pref[j] = pref[j-1] + v[i][j-1];
  30.             suff[j] = suff[j-1] + v[i][s-j];
  31.         }
  32.         best[i][0] = 0;
  33.         // try all splits: take L from left, R from right, L+R = k
  34.         for(int k = 1; k <= s; k++){
  35.             ll mx = 0;
  36.             for(int L = 0; L <= k; L++){
  37.                 int R = k - L;
  38.                 if(R > s) continue;
  39.                 mx = max(mx, pref[L] + suff[R]);
  40.             }
  41.             best[i][k] = mx;
  42.         }
  43.     }
  44.  
  45.     vector<ll> dp(m+1, NEG_INF);
  46.     dp[0] = 0;
  47.     for(int i = 0; i < n; i++){
  48.         // iterate backwards so we don't reuse shelf i more than once
  49.         for(int used = m; used >= 0; used--){
  50.             if(dp[used] == NEG_INF) continue;
  51.             // try smashing k items from shelf i
  52.             for(int k = 1; k <= sz[i] && used + k <= m; k++){
  53.                 dp[used + k] = max(dp[used + k],
  54.                                    dp[used] + best[i][k]);
  55.             }
  56.         }
  57.     }
  58.  
  59.     // 3) Answer is dp[m]
  60.     cout << dp[m] << "\n";
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
2 3
3 3 7 2
3 4 1 5
stdout
copy 
15
https://ideone.com/U0p9mq
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!