CF1442D #9 WA 求调
查看原帖
CF1442D #9 WA 求调
388889
daishuchen2010楼主2024/1/24 19:34
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 5;
int n,k,len[MAXN];
long long sum[MAXN],dp[MAXN][MAXN],ans,pre[MAXN][MAXN];
void dfs(int l,int r,int dep)
{
	if (l == r)
	{
		for (int i = 0; i <= min(len[l],k); i++) ans = max(ans,dp[dep][k - i] + pre[l][i]);
		return ;
	}
	int mid = (l + r) / 2;
	for (int j = 0; j <= k; j++) dp[dep + 1][j] = dp[dep][j];
	for (int i = l; i <= mid; i++)
	{
		for (int j = k; j >= len[i]; j--)
		{
			dp[dep + 1][j] = max(dp[dep + 1][j],dp[dep + 1][j - len[i]] + sum[i]);
		}
	}
	dfs(mid + 1,r,dep + 1);
	for (int j = 0; j <= k; j++) dp[dep + 1][j] = dp[dep][j];
	for (int i = mid + 1; i <= r; i++)
	{
		for (int j = k; j >= len[i]; j--)
		{
			dp[dep + 1][j] = max(dp[dep + 1][j],dp[dep + 1][j - len[i]] + sum[i]);
		}
	}
	dfs(l,mid,dep + 1);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int y;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> len[i];
		for (int j = 1; j <= len[i]; j++)
		{
			cin >> y;
			pre[i][j] = pre[i][j - 1] + y;
			sum[i] += y;
		}
	}
	dfs(1,n,0);
	cout << ans << '\n';
	return 0;
}
2024/1/24 19:34
加载中...