Advertisement
limimage

ZADACHA

Sep 25th, 2019
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl "\n"
  4. using namespace std;
  5. using ll = long long;
  6. using ld = long double;
  7. using pii = pair<int, int>;
  8.  
  9. constexpr int N = 1e3+5;
  10.  
  11. int a, b, c, n, weight[N];
  12. int dp[N][N];
  13. vector<int> ans;
  14.  
  15. void Solve()
  16. {
  17. cin >> a >> b >> c >> n;
  18. if (a > c)
  19. {
  20. cout << a << endl << 0;
  21. return;
  22. }
  23. for (int i = 1; i <= n; i++)
  24. cin >> weight[i];
  25. for (int i = 0; i < N; i++)
  26. fill(dp[i], dp[i] + N, INT32_MAX);
  27. dp[0][0] = 0;
  28. for (int i = 1; i <= n; i++)
  29. for (int j = 0; j < N; j++)
  30. {
  31. if (weight[i] <= j && dp[i - 1][j - weight[i]] != INT32_MAX)
  32. dp[i][j] = j;
  33. else dp[i][j] = dp[i - 1][j];
  34. }
  35. for (int i = c - a + 1; i < N; i++)
  36. {
  37. if (dp[n][i] <= b)
  38. {
  39. cout << a + i << endl;
  40. for (int j = n; dp[j][i] != 0; j--)
  41. {
  42. if (dp[j][i] == dp[j - 1][i])
  43. continue;
  44. assert(dp[j][i] != INT32_MAX);
  45. ans.push_back(j);
  46. i -= weight[j];
  47. }
  48. reverse(ans.begin(), ans.end());
  49. cout << ans.size();
  50. for (int el: ans)
  51. cout << " " << el;
  52. return;
  53. }
  54. }
  55. cout << a + b << endl << -1;
  56. }
  57.  
  58. int main()
  59. {
  60. ios::sync_with_stdio(false);
  61. cin.tie(nullptr);
  62. cout.tie(nullptr);
  63. Solve();
  64. return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement