Untitled

 avatar
unknown
c_cpp
a year ago
654 B
3
Indexable
#include <stdio.h>
#include <string.h>

int n, k, a[21], t[21], dp[21][10001];
int max(int a, int b)
{return a > b ? a : b;}
int solve(int i, int j)
{
    if (i > n)
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    if (j < t[i])
        return dp[i][j] = solve(i + 1, j);
    else
        return dp[i][j] = max(solve(i + 1, j), solve(i + 1, j - t[i]) + a[i]);
}
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &t[i]);
    memset(dp, -1, sizeof(dp));
    printf("%d\n", solve(1, k));
    return 0;
}
Editor is loading...