Advertisement
bibaboba12345

Untitled

Jun 16th, 2022
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cassert>
  7.  
  8. const int N = 101, K = 15;
  9. using namespace std;
  10.  
  11.  
  12. pair<int, int> p[1 << K][N];
  13. long long dp[1 << K][N], n, k;
  14.  
  15. int a[N], b[K], answ[K], sum[N];
  16.  
  17. bool check(int mask, int ind) {
  18. return mask & (1 << ind);
  19. }
  20.  
  21. int main()
  22. {
  23. #ifdef _DEBUG
  24. freopen("input.txt", "r", stdin);
  25. #else
  26. std::ios::sync_with_stdio(false);
  27. cin.tie(0);
  28. #endif
  29. cin >> n >> k;
  30. for (int i = 0; i < k; i++) {
  31. cin >> b[i];
  32. answ[i] = -1;
  33. }
  34. for (int i = 0; i < n; i++) {
  35. cin >> a[i];
  36. }
  37.  
  38. for (int i = 0; i < n; i++) {
  39. for (int mask = 0; mask < (1 << k); mask++) {
  40. dp[mask][i] = 1e18;
  41. }
  42. }
  43. dp[0][0] = 0;
  44. for (int i = 0; i < n; i++) {
  45. for (int mask = 0; mask < 1 << k; mask++) {
  46. if (dp[mask][i] > a[i]) {
  47. continue;
  48. }
  49. if (dp[mask][i + 1] > 0) {
  50. dp[mask][i + 1] = 0;
  51. p[mask][i + 1] = { -1,-1 };
  52. }
  53. for (int j = 0; j < k; j++) {
  54. if (!check(mask, j)) {
  55. if (dp[mask ^ (1 << j)][i] > dp[mask][i] + b[j]) {
  56. p[mask ^ (1 << j)][i] = { mask,i };
  57. dp[mask ^ (1 << j)][i] = dp[mask][i] + b[j];
  58. }
  59. }
  60. }
  61. }
  62. }
  63. if (dp[(1 << k) - 1][n - 1] > a[n - 1]) {
  64. cout << "NO";
  65. return 0;
  66. }
  67. int mask = (1 << k) - 1;
  68. int v = n - 1;
  69. while (mask != 0) {
  70. if (p[mask][v].first == -1) {
  71. v--;
  72. continue;
  73. }
  74. int nu_mask = p[mask][v].first;
  75. int XORed = nu_mask ^ mask;
  76. for (int j = 0; j < k; j++) {
  77. if (check(XORed, j)) {
  78. assert(answ[j] == -1);
  79. answ[j] = v + 1;
  80. }
  81. }
  82. mask = nu_mask;
  83. }
  84.  
  85. for (int i = 0; i < k; i++) {
  86. sum[answ[i] - 1] += b[i];
  87. }
  88.  
  89. for (int i = 0; i < n; i++) {
  90. assert(sum[i] <= a[i]);
  91. }
  92.  
  93. cout << "YES\n";
  94. for (int i = 0; i < k; i++) {
  95. assert(answ[i] > 0);
  96. cout << answ[i] << " ";
  97. }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement