Advertisement
Guest User

Untitled

a guest
Apr 21st, 2018
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12. int n, k;
  13. cin >> n >> k;
  14. vector<int> a(n + 1);
  15. vector<vector<int> > dp(k + 1, vector<int> (n + 1, -2e9));
  16. dp[0][0] = 0;
  17. for (int i = 1; i <= n; ++i)
  18. {
  19. cin >> a[i];
  20. }
  21.  
  22. if (k < n || k >= 400)
  23. {
  24. cout << "Impossible";
  25. return 0;
  26. }
  27.  
  28. for (int i = 1; i <= k; ++i)
  29. {
  30. for (int j = 1; j <= n; ++j)
  31. {
  32. for (int q = 1; q <= n; ++q)
  33. {
  34. if (i >= q + 1 && j >= q)
  35. {
  36. dp[i][j] = max(dp[i][j], dp[i - q - 1][i - q] + a[q]);
  37. }
  38. if (i >= q && j >= q)
  39. {
  40. dp[i][j] = max(dp[i][j], dp[i - q][j - q] + a[q]);
  41. }
  42. }
  43. }
  44. }
  45. int maxn = 450;
  46. bool dp1[maxn][maxn];
  47. dp1[0][0] = 1;
  48. for (int i = 1; i < maxn; ++i) {
  49. for (int j = 1; j < maxn; ++j) {
  50. for (int k = 1; k < maxn; ++k) {
  51. if (i >= k && j >= k)
  52. dp1[i][j] = max(dp1[i][j], dp1[i - k][j - k]);
  53. if (i >= k + 1 && j >= k)
  54. dp1[i][j] = max(dp1[i][j], dp1[i - k - 1][j - k]);
  55. }
  56. }
  57. }
  58. int ans = -1;
  59. for (int i = 0; i <= k; ++i)
  60. {
  61. for (int j = 0; j <= n; ++j)
  62. {
  63. if (dp1[k - i][n - j])
  64. {
  65. ans = max(ans, dp[i][j]);
  66. }
  67. }
  68. }
  69. cout << ans;
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement