目录
C DP
The 2022 ICPC Asia Hangzhou Regional Programming Contest
C. No Bug No Game
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int N = 3e3 + 5, inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int n, k, dp[N][N][2];
vector<int> p[N];
void solve(){
cin >> n >> k;
int sum = 0;
for(int i = 1; i <= n; ++ i){
int c, t;
cin >> c;
for(int j = 0; j < c; ++ j){
cin >> t;
p[i].push_back(t);
}
sum += c;
}
if(sum <= k){
sum = 0;
for(int i = 1; i <= n; ++ i) sum += p[i].back();
cout << sum << '\n';
return ;
}
mem(dp, -1);
dp[0][0][0] = 0;
for(int i = 1; i <= n; ++ i){
int c = p[i].size();
for(int j = 0; j <= k; ++ j){
dp[i][j][0] = dp[i - 1][j][0];
if(j >= c && dp[i - 1][j - c][0] != -1)
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - c][0] + p[i].back());
}
}
dp[n + 1][0][1] = 0;
for(int i = n; i > 0; -- i){
int c = p[i].size();
for(int j = 0; j <= k; ++ j){
dp[i][j][1] = dp[i + 1][j][1];
if(j >= c && dp[i + 1][j - c][1] != -1)
dp[i][j][1] = max(dp[i][j][1], dp[i + 1][j - c][1] + p[i].back());
}
}
int ans = 0;
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= p[i].size(); ++ j){
int res = k - j;
for(int l = 0; l <= res; ++ l){
int r = res - l;
if(dp[i - 1][l][0] != -1 && dp[i + 1][r][1] != -1){
ans = max(ans, dp[i - 1][l][0] + dp[i + 1][r][1] + p[i][j - 1]);
}
}
}
}
cout << ans << '\n';
return ;
}
signed main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}