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
| #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi;
#define rep(i, a, n) for (int i = a; i < n; ++i) #define per(i, a, n) for (int i = n - 1; i >= a; --i) #define fi first #define se second
const int maxn = 1e4 + 5; const int maxm = 200;
int a, b; int mark[maxn]; int m, n, t; int dp[maxn], v[maxn], w[maxn];
int main() { ios::sync_with_stdio(false);
while (cin >> a >> b) { int tt = b / a;
cin >> m >> t;
rep(i, 1, t + 1) { cin >> mark[i]; } int sum = 0; w[0] = 0; rep(i, 1, m + 1) { cin >> w[i] >> v[i]; w[i] = mark[w[i]]; w[0] += w[i]; }
cin >> n; n /= tt; memset(dp, 0, sizeof(dp)); rep(i, 1, m + 1) { sum += w[i]; per(j, max(w[i], n - w[0] + sum), n + 1) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[n] << endl; } }
|