Untitled

 avatar
unknown
plain_text
2 years ago
1.5 kB
5
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <array>
#include <bitset>
using namespace std;

typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> pii;
typedef pair<LL, LL> pll;
#define pub push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
const LD EPS = 1e-9;
const int INF = 1e9 + 7;
const LL LINF = 1e18;
const int N = 3010;
const LD PI = acosl(-1.0);
#define int64 long long


int n, m;
int dp[N][N];
int L[N];
bool usedT[N];;


int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &L[i]);
	scanf("%d", &m);
	for (int i = 0; i < m; ++i)
	{
		int t; scanf("%d", &t);
		usedT[t] = true;
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < N; ++j)
			dp[i][j] = -1;
	}
	dp[0][0] = 0;
	dp[0][L[0]] = (usedT[L[0]] == true ? 1 : 0);
	for (int i = 1; i < n; ++i)
	{
		for (int t = 0; t < N; ++t)
		{
			if (dp[i - 1][t] != -1)
				dp[i][t] = dp[i - 1][t];
			if (t >= L[i] && dp[i - 1][t - L[i]] != -1)
				dp[i][t] = max(dp[i][t], dp[i - 1][t - L[i]] + (usedT[t] == true ? 1 : 0));
		}
	}
	int ans = 0;
	for (int t = 0; t < N; ++t)
		ans = max(ans, dp[n - 1][t]);
	printf("%d", ans);
	return 0;
}
Editor is loading...