Spoj_Solutions/BAT1.cpp at master · susmith98/Spoj_Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// https://www.spoj.com/problems/BAT1/

#include <bits/stdc++.h>
using namespace std;
int Dp[21][21][1001],Dp1[21][1001];
int C[21][21],P[21][21],Bi[21];
int N,M,K;
void FillDp(int bi,int m)
{
	if(m<=0)
	{
		return;
	}
	for(int i=M;i>0;i--)
	{
		for(int j=1;j<=m;j++)
		{
			if(i==M)
			{
				if(j<C[bi][i])
				{
					Dp[bi][i][j] =0;
				}
				else{
					Dp[bi][i][j] = (j/C[bi][i])*P[bi][i];
				}
			}
			else{
				if(j<C[bi][i])
				{
					Dp[bi][i][j]=Dp[bi][i+1][j];
				}
				else{
					Dp[bi][i][j]=max(P[bi][i]+Dp[bi][i][j-C[bi][i]],Dp[bi][i+1][j]);
				}
			}
		}
	}
}
int main() {
	int T;
	cin>>T;
	while(T--)
	{
		cin>>N>>M>>K;
		for(int i=1;i<=N;i++)
		{
			cin>>Bi[i];
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=M;j++)
			{
				cin>>C[i][j];
			}
		}
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=M;j++)
			{
				cin>>P[i][j];
			}
		}
		for(int i=1;i<=N;i++)
		{
			FillDp(i,K-Bi[i]);
		}
		for(int i=N;i>0;i--)
		{
			for(int j=1;j<=K;j++)
			{
				if(i==N){
					if(j<=Bi[i])
					{
						Dp1[i][j] = 0;
					}
					else{
						Dp1[i][j] = Dp[i][1][j-Bi[i]];
					}
				}
				else{
					if(j<=Bi[i])
					{
						Dp1[i][j] = Dp1[i+1][j];
					}
					else{
						Dp1[i][j] = max(Dp1[i+1][j],Dp[i][1][j-Bi[i]]);
					}
				}
			}
		}

		cout<<Dp1[1][K]<<"\n";
	}
	return 0;
}