Advertisement
nicuvlad76

Untitled

Dec 2nd, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("bete.in");
  4. ofstream fout("bete.out");
  5.  
  6. int n,S;
  7. int v[103];
  8. int a[10003];
  9. int sol[103];
  10.  
  11. int main()
  12. {
  13. int i,ult;
  14. int x,j,k;
  15.  
  16. fin >> n >> S;
  17. for (i = 1; i <= n; i++)
  18. fin >> v[i];
  19.  
  20. a[v[1]] = 1; ult = v[1];
  21. for (i = 2; i <= n; i++)
  22. {
  23. x = v[i];
  24. for (j = ult; j >= 1; j--)
  25. if (a[j] != 0 && j+x <= S) a[j+x] = i;
  26. a[x] = i;
  27. ult = min(S,ult+x);
  28. }
  29.  
  30. if (a[S] == 0) fout << "NU\n";
  31. else
  32. {
  33. fout << "DA\n";
  34.  
  35. k = 0;
  36. while (S != 0)
  37. {
  38. sol[++k] = a[S];
  39. S-=v[a[S]];
  40. }
  41.  
  42. fout << k << "\n";
  43. for (i = k; i >= 1; i--)
  44. fout << sol[i] << " ";
  45. }
  46.  
  47. return 0;
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement