Advertisement
_Sarvar_

Untitled

Jan 23rd, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 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. const int N = 1001;
  9. const int INF = 1000009;
  10.  
  11. pair <int, vector <int> > p[INF];
  12. int t[N], d[INF];
  13. int a, b, c, n;
  14.  
  15. int main() {
  16. cin >> a >> b >> c >> n;
  17. if (a > c) {
  18. cout << -1;
  19. return 0;
  20. }
  21. for (int i = 1; i <= n; i++) {
  22. cin >> t[i];
  23. }
  24. // d[a] = 1;
  25. d[0] = 1;
  26. for (int i = 1; i <= n; i++) {
  27. for (int j = 2002; j >= 0; j--) {
  28. if (j + t[i] < 2002 && d[j] == 1) {
  29. d[j + t[i]] = 1;
  30. p[j + t[i]].fi = j;
  31. p[j + t[i]].sc.pb(i);
  32. }
  33. }
  34. }
  35. vector <int> v;
  36. for (int i = c - a + 1; i <= 2002; i++) {
  37. if (d[i] && i + a < (a + b)) {
  38. cout << i + a << "\n";
  39. int x = p[i].sc.back(), y = p[i].fi;
  40. // cout << x << " " << y << "\n";
  41. p[i].sc.pop_back();
  42. while (x) {
  43. // cout << "asdf";
  44. v.push_back(x);
  45. int y1 = y;
  46. if (p[y].sc.empty()) break;
  47. x = p[y].sc.back(), y = p[y].fi;
  48. p[y1].sc.pop_back();
  49. // cout << x << " " << y << "\n";
  50. }
  51. sort(v.begin(), v.end());
  52. cout << v.size() << " ";
  53. for (int i = 0; i < v.size(); i++)
  54. cout << v[i] << " ";
  55. return 0;
  56. }
  57. }
  58. cout << -1;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement