fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. struct Node {
  8.     int val, i, j;
  9.     Node() : val(0), i(0), j(0) {}
  10.     Node(int i, int j) : val(0), i(i), j(j) {}
  11.     Node(int& val, int i, int& j) : val(val), i(i), j(j) {};
  12. };
  13.  
  14. int main() {
  15.     int n, m; cin >> n >> m;
  16.     vector <int> w(n), c(n);
  17.     for (int i = 0; i < n; i++) {
  18.         cin >> w[i];
  19.     }
  20.     for (int i = 0; i < n; i++) {
  21.         cin >> c[i];
  22.     }
  23.     vector <vector<Node>> dp(n, vector<Node>(m + 1));
  24.     for (int i = 0; i < n; i++) {
  25.         dp[i][0] = Node(i, 0);
  26.     }
  27.     for (int j = 1; j <= m; j++) {
  28.         dp[0][j] = Node(0, j);
  29.     }
  30.     for (int i = 1; i < n; i++) {
  31.         for (int j = 1; j <= m; j++) {
  32.             int buf = dp[i - 1][j].val, jj = j;
  33.             if (j - w[i] >= 0 and dp[i - 1][j - w[i]].val + c[i] >= buf) {
  34.                 buf = dp[i - 1][j - w[i]].val + c[i];
  35.                 jj = j - w[i];
  36.             }
  37.             dp[i][j] = Node(buf, i - 1, jj);
  38.         }
  39.     }
  40.     vector <int> path;
  41.     int i = n - 1, j = m;
  42.     while (i > 0 and j > 0) {
  43.         Node buf = dp[i][j];
  44.         if (buf.i == i - 1 and buf.j != j) {
  45.             path.push_back(i + 1);
  46.             j = buf.j;
  47.         }
  48.         i = buf.i;
  49.     }
  50.  
  51.     reverse(path.begin(), path.end());
  52.     cout << path.size() << endl;
  53.     for (auto c : path) {
  54.         cout << c << ' ';
  55.     }
  56.     return 0;
  57. }
  58.  
  59. //отправляю, чтобы сохранить
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
4 6
2 4 1 2
7 2 5 1
stdout
copy 
2
2 3
https://ideone.com/ONVHVB
language:
C++ (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!