473

This solution is based on 0/1 knapsack problem.

dp[i][j][k] is the maximum amount of songs with i songs while k unit time is left in disk j.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>

using namespace std;

int N,T,M;
int song[800];
int dp[800][100][100];

void DP()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			for(int k=0;k<=T;k++)
			{
				if(k<song[i])
				dp[i+1][j][k]=dp[i][j][k];
				else if(k>=song[i])
				dp[i+1][j][k]=max(dp[i][j][k-song[i]]+1,dp[i][j][k]);
				if(j)
				dp[i+1][j][k]=max(dp[i][j-1][T-song[i]]+1,dp[i+1][j][k]);
			}
		}
	}
}

int main()
{
	int tt;
	cin>>tt;

	while(tt--)
	{
		cin>>N>>T>>M;
		cin>>song[0];
		for(int i=1;i<N;i++)
		{
			scanf(", %d",&song[i]);
		}
		memset(dp,0,sizeof(dp));
		DP();

		int res = 0;
		for(int i=0;i<=N;i++)
		{
			res = max(res,dp[i][M][0]);
		}
		cout<<res<<"\n";
		if(tt)
		cout<<"\n";
	}
	return 0;
}