Advertisement
Guest User

Untitled

a guest
Dec 11th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <iostream>
  2. //#include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6.  
  7. long Max(long a, long b){
  8.     if (a > b) return a;
  9.     else return b;
  10. }
  11.  
  12. struct thing{
  13.     int m;
  14.     int n;
  15. };
  16.  
  17. int main() {
  18.     int N;
  19.     cin >> N;
  20.     int M;
  21.     cin >> M;
  22.     thing t[N];
  23.     for (int i = 0; i < N; ++i){
  24.         cin >> t[i].m;
  25.     }
  26.     for (int i = 0; i < N; ++i){
  27.         cin >> t[i].n;
  28.     }
  29.     long max[N + 1][M + 1];
  30.     for (int i = 0; i < M + 1; ++i){
  31.         max[0][i] = 0;
  32.     }
  33.     for (int i = 0; i < N + 1; ++i){
  34.         max[i][0] = 0;
  35.     }
  36.     for (int i = 1; i <= N; ++i){
  37.         for (int j = 1; j <= M; ++j){
  38.             if (t[i - 1].m > j) max[i][j] = max[i - 1][j];
  39.             else max[i][j] = Max(max[i - 1][j], max[i - 1][j - t[i - 1].m] + t[i - 1].n);
  40.         }
  41.     }
  42.     bool ans[N];
  43.     int currM = M;
  44.     for (int i = N; i > 0; --i){
  45.         if (max[i][currM] == max[i - 1][currM]) ans[i - 1] = false;
  46.         else {
  47.             ans[i - 1] = true;
  48.             currM -= t[i - 1].m;
  49.         }
  50.     }
  51.     for (int i = 0; i < N; ++i){
  52.         if (ans[i]) cout << i + 1 << endl;
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement