Участник:Andriygav/BAT1

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/BAT1/

#include <iostream>
using namespace std;
 
int yes, cost[32], seen[2][32][32][1024], a[32][32], w[32][32], money[2][32][32][1024];
 
int calc_money(int t, int i, int j, int k, int n, int m) {
	if(seen[t][i][j][k] == yes){
		return money[t][i][j][k];
	}
	seen[t][i][j][k] = yes;
	money[t][i][j][k] = -1073741824;
 
	if(i == 0){
		if(t == 1){
			return -1073741824;
 
		}
		money[t][i][j][k] = 0;
		return money[t][i][j][k];
	}
 
	if(t == 0){ 
		money[t][i][j][k] = max(calc_money(0, i - 1, n, k, n, m), calc_money(1, i - 1, n, k, n, m));
		return money[t][i][j][k];
	}
 
	if(k >= cost[i]){
		money[t][i][j][k] = max(calc_money(0, i - 1, n, k - cost[i], n, m), calc_money(1, i - 1, n, k - cost[i], n, m));
	}
 
	if(j == 0){
		return money[t][i][j][k];
	}
 
	money[t][i][j][k] = max(money[t][i][j][k], calc_money(t, i, j - 1, k, n, m));
	for(int l = 1; l <= 1; l++){
		if(k - cost[i] - l*a[i][j] >= 0 && calc_money(0, i, j - 1, k - cost[i] - l*a[i][j], n, m) > -1073741824){
			money[t][i][j][k] = max(money[t][i][j][k], calc_money(0, i, j - 1, k - cost[i] - l*a[i][j], n, m) + l*w[i][j]);
		}
 
		if(k - l*a[i][j] >= 0 && calc_money(1, i, j - 1, k - l*a[i][j], n, m) > -1073741824){
			money[t][i][j][k] = max(money[t][i][j][k], calc_money(1, i, j - 1, k - l*a[i][j], n, m) + l*w[i][j]);
		}
 
		if(k - l*a[i][j] >= 0 && calc_money(1, i, j, k - l*a[i][j], n, m) > -1073741824){
			money[t][i][j][k] = max(money[t][i][j][k], calc_money(1, i, j, k - l*a[i][j], n, m) + l*w[i][j]);
		}
	}
	return money[t][i][j][k];
}
 
int main() {
	int m, n, K;
	int t;
	cin >> t;
    while(t--){
    	yes++;
    	cin >> m >> n >> K;
		for(int i = 1; i <= m; i++){
			cin >> cost[i];
		}
 
		for(int i = 1; i <= m; i++){
			for(int j = 1; j <= n; j++){
				cin >> a[i][j];
			}
		}
 
		for(int i = 1; i <= m; i++){
			for(int j = 1; j <= n; j++){
				cin >> w[i][j];
			}
		}
 
		int ans = -1073741824;
		for(int k = K; k >= 0; k--){
			ans = max(ans, max(calc_money(0, m, n, k, n, m), calc_money(1, m, n, k, n, m)));
		}
		cout << ans << endl;
 
    }
	return 0;
}