Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 1;
- const int INF = 2e9;
- int dp[1005][maxn];
- int main() {
- int n, x;
- cin >> n >> x;
- vector<int> prices(n), pages(n);
- for(int i = 0; i < n; i++) {
- cin >> prices[i];
- }
- for(int i =0 ; i < n; i++) {
- cin >> pages[i];
- }
- for(int i = 0; i <= n; i++) {
- for(int j = 0; j < maxn; j++) {
- dp[i][j] = -INF;
- }
- }
- dp[0][x] = 0;
- for(int at = 0; at < n; at++) {
- for(int sum = x; sum >= 0; sum--) {
- if(sum - prices[at] >= 0) {
- dp[at + 1][sum - prices[at]] = max(dp[at + 1][sum - prices[at]], dp[at][sum] + pages[at]);
- }
- dp[at + 1][sum] = max(dp[at + 1][sum], dp[at][sum]);
- }
- }
- int res = -INF;
- for(int sum = 0; sum <= x; sum++) {
- res = max(res, dp[n][sum]);
- }
- cout << res << endl;
- return 0;
- }
- // 2 1 3 3
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement