Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- //#include <cmath>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- long Max(long a, long b){
- if (a > b) return a;
- else return b;
- }
- struct thing{
- int m;
- int n;
- };
- int main() {
- int N;
- cin >> N;
- int M;
- cin >> M;
- thing t[N];
- for (int i = 0; i < N; ++i){
- cin >> t[i].m;
- }
- for (int i = 0; i < N; ++i){
- cin >> t[i].n;
- }
- long max[N + 1][M + 1];
- for (int i = 0; i < M + 1; ++i){
- max[0][i] = 0;
- }
- for (int i = 0; i < N + 1; ++i){
- max[i][0] = 0;
- }
- for (int i = 1; i <= N; ++i){
- for (int j = 1; j <= M; ++j){
- if (t[i - 1].m > j) max[i][j] = max[i - 1][j];
- else max[i][j] = Max(max[i - 1][j], max[i - 1][j - t[i - 1].m] + t[i - 1].n);
- }
- }
- bool ans[N];
- int currM = M;
- for (int i = N; i > 0; --i){
- if (max[i][currM] == max[i - 1][currM]) ans[i - 1] = false;
- else {
- ans[i - 1] = true;
- currM -= t[i - 1].m;
- }
- }
- for (int i = 0; i < N; ++i){
- if (ans[i]) cout << i + 1 << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement