Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1.  
  2.  
  3. #pragma comment(linker, "/STACK:10000000000")
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #include <iostream>
  6. #include <set>
  7. #include <vector>
  8. #include <map>
  9. #include <algorithm>
  10. using namespace std;
  11. pair <bool,int> c[10001];
  12. bool f[10001];
  13. int main()
  14. {
  15.  
  16. #ifdef _DEBUG
  17. // freopen("input.txt", "r", stdin);
  18. // freopen("output.txt", "w", stdout);
  19. #else
  20. // freopen("segments.in", "r", stdin);
  21. // freopen("segments.out", "w", stdout);
  22. #endif
  23. int n, a, b[10001], sum, i, j, ans, t;
  24. cin >> n >> a >> t;
  25. a -= t;
  26. n--;
  27. sum = 0;
  28. c[0].first = 1;
  29. for (i = 0; i < n; i++)
  30. {
  31. cin >> b[i];
  32. for (j = sum; j >= 0; j--)
  33. {
  34. if (c[j].first && !c[j + abs(b[i])].first)
  35. {
  36. c[j + abs(b[i])].first = 1;
  37. c[j + abs(b[i])].second = i;
  38. }
  39. }
  40. sum += abs(b[i]);
  41. }
  42. ans = 0;
  43. int ans_2 = sum + a;
  44. for (i = 0; i <= sum; i++)
  45. {
  46. if (c[i].first == 1 && abs(2 * i - ans_2) < abs(2 * ans - ans_2))
  47. {
  48. ans = i;
  49. }
  50.  
  51. }
  52. cout << ans * 2 - sum + t << endl << t;
  53. while (ans > 0)
  54. {
  55. f[c[ans].second] = 1;
  56. ans -= abs(b[c[ans].second]);
  57. }
  58. for (i = 0; i < n; i++)
  59. {
  60. if (f[i]==1)
  61. {
  62. if (b[i] >= 0)
  63. {
  64. cout << '+' << b[i];
  65. }
  66. else
  67. {
  68. cout << '-' << b[i];
  69. }
  70. }
  71. else
  72. {
  73. if (b[i] >= 0)
  74. {
  75. cout << '-' << b[i];
  76. }
  77. else
  78. {
  79. cout << '+' << b[i];
  80. }
  81. }
  82. }
  83. #ifdef _DEBUG
  84. system("pause");
  85. #endif
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement