Advertisement
Guest User

Untitled

a guest
Apr 21st, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 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. long long n, k;
  13. cin >> n >> k;
  14. vector<long long> a(n + 1);
  15. vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, 1e9));
  16. dp[0][0] = 0;
  17. for (int i = 1; i <= n; ++i)
  18. {
  19. cin >> a[i];
  20. }
  21. if (k < n || n + 1 < k)
  22. {
  23. cout << "Impossible";
  24. return 0;
  25. }
  26. for (int i = 1; i <= k; ++i)
  27. {
  28. for (int j = 1; j <= n; ++j)
  29. {
  30. for (int q = 1; q <= n; ++q)
  31. {
  32. if (i >= q + 1 && j >= q)
  33. {
  34. dp[i][j] = max(dp[i][j], dp[i - q - 1][i - q] + a[q - 1]);
  35. }
  36. else if (i >= q && j >= q)
  37. {
  38. dp[i][j] = max(dp[i][j], dp[i - q][j - q] + a[q - 1]);
  39. }
  40. }
  41. }
  42. }
  43. long long ans = -1;
  44. for (int i = 0; i < n; ++i)
  45. {
  46. for (int j = 0; j < n; ++j)
  47. {
  48. if (k - i == n - j || k - i + 1 == n - j)
  49. {
  50. if (dp[i][j] < 1e9)
  51. {
  52. ans = max(ans, dp[i][j]);
  53. }
  54. }
  55. }
  56. }
  57. cout << ans ;
  58. return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement