Advertisement
_Sarvar_

Untitled

Jan 23rd, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define sc second
  4. #define fi first
  5.  
  6. using namespace std;
  7.  
  8. struct parent {
  9. int x, y, c;
  10. };
  11.  
  12. const int N = 1001;
  13. const int INF = 3009;
  14.  
  15. long long t[N], d[N][INF];
  16. parent p[N][INF];
  17. long long a, b, c, n;
  18.  
  19. int main() {
  20. cin >> a >> b >> c >> n;
  21. if (a > c || a + b < c) {
  22. cout << a + b << "\n";
  23. cout << -1;
  24. return 0;
  25. }
  26. for (int i = 1; i <= n; i++) {
  27. cin >> t[i];
  28. }
  29. for (int i = 1; i <= n; i++) {
  30. for (int j = 0; j <= a + b; j++) {
  31. if ((j - t[i] >= 0)
  32. && (d[i - 1][j - t[i]] + t[i] > d[i - 1][j])) {
  33. d[i][j] = d[i - 1][j - t[i]] + t[i];
  34. p[i][j].x = i - 1;
  35. p[i][j].c = i;
  36. p[i][j].y = j - t[i];
  37. }
  38. else {
  39. d[i][j] = d[i - 1][j];
  40. p[i][j].x = i - 1;
  41. p[i][j].c = -1;
  42. p[i][j].y = j;
  43. }
  44. }
  45. }
  46. int ans = -1, ax, ay;
  47. for (int j = c - a + 1; j < a + b; j++) {
  48. if (d[n][j] && d[n][j] < a + b) {
  49. cout << j + a << "\n";
  50. vector <int> v;
  51. ax = n; ay = j;
  52. while (ax && ay) {
  53. if (p[ax][ay].c != -1)
  54. v.push_back(p[ax][ay].c);
  55. int ax1 = p[ax][ay].x;
  56. ay = p[ax][ay].y;
  57. ax = ax1;
  58. }
  59. sort(v.begin(), v.end());
  60. cout << v.size() << " ";
  61. for (int i = 0; i < v.size(); i++)
  62. if (v[i] != -1)
  63. cout << v[i] << " ";
  64.  
  65. return 0;
  66. }
  67. }
  68. cout << a + b << "\n";
  69. cout << -1;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement