Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define LOCAL
- #define INPUT 1
- #define OUTPUT 0
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- #define forn(i, n) for (int i = 0; i < n; i++)
- #define fornn(i, q, n) for (int i = q; i < n; i++)
- #define ll long long
- #define mp make_pair
- #define pb push_back
- #define all(v) v.begin(), v.end()
- #define times clock() * 1.0 / CLOCKS_PER_SEC
- #define TASK "gg"
- using namespace std;
- const double eps = 1e-7;
- const double pi = acos(-1.0);
- const int INF = 2e9 + 1;
- const ll LINF = 8e18;
- const ll MM = 1e9 + 7;
- int solve();
- int main()
- {
- #ifdef LOCAL
- if (INPUT)
- //freopen(TASK".in", "r", stdin);
- freopen("input.txt", "r", stdin);
- if (OUTPUT)
- //freopen(TASK".out", "w", stdout);
- freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- #else
- if (INPUT)
- freopen(TASK".in", "r", stdin);
- if (OUTPUT)
- freopen(TASK".out", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- #endif
- solve();
- #ifdef LOCAL
- cerr.precision(3);
- cerr << "\nTIME: " << times << "\n";
- #endif
- return 0;
- }
- ll dp[10007], weights[107], c[107], path[10007];
- void go(int i)
- {
- if (path[i] != -1)
- {
- go(i - weights[path[i]]);
- cout << path[i] + 1 << "\n";
- }
- }
- int solve()
- {
- int n,v;
- cin >> v >> n;
- forn(i, v)
- cin >> weights[i];
- forn(i, v)
- cin >> c[i];
- forn(i, n + 1)
- {
- path[i] = -1;
- dp[i] = -1;
- }
- dp[0] = 0;
- forn(i, v)
- for (int w = n; w >= weights[i]; w--)
- if (dp[w - weights[i]] != -1)
- {
- if (dp[w - weights[i]] + c[i] >= dp[w])
- {
- dp[w] = dp[w - weights[i]] + c[i];
- path[w] = i;
- }
- }
- int ind = n;
- for(int i = n; i >= 0; i--)
- if (dp[i] > dp[ind])
- ind = i;
- go(ind);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement