Advertisement
Sitleman

Untitled

Nov 13th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <fstream>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <unordered_set>
  9. #include <tuple>
  10. #include <unordered_map>
  11. #include <deque>
  12. #include <cmath>
  13. using namespace std;
  14. const long long INF = 1e18;
  15. int main() {
  16. ios::sync_with_stdio(0);
  17. cin.tie(0);
  18. cout.tie(0);
  19. ifstream cin("input.txt");
  20. ofstream cout("output.txt");
  21. int n, k;
  22. cin >> n >> k;
  23.  
  24. if (k == 0) {
  25. for (int i = 1; i <= n; i++) {
  26. cout << 0 << " " << 0 << '\n';
  27. }
  28. return 0;
  29. }
  30. vector<vector<int>> a(n + 1, vector<int> (2));
  31. vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>> (k + 1, vector<long long> (4, INF)));
  32. vector<vector<vector<long long>>> p(n + 1, vector<vector<long long>> (k + 1, vector<long long> (4, INF)));
  33. cin >> a[1][0] >> a[1][1];
  34. dp[1][0][0] = a[1][0] + a[1][1];
  35.  
  36. dp[1][1][3] = 0;
  37.  
  38. for (int i = 2; i <= n; i++){
  39. cin >> a[i][0] >> a[i][1];
  40. for (int j = 0; j <= k; j++){
  41. dp[i][j][0] = min(min(dp[i - 1][j][0], dp[i - 1][j][1]),
  42. min(dp[i - 1][j][2], dp[i - 1][j][3]));
  43. dp[i][j][0] += a[i][0] + a[i][1];
  44.  
  45. if (j >= 1) dp[i][j][1] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][2]) + a[i][1] - a[i - 1][0];
  46. if (j >= 1) dp[i][j][2] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + a[i][0] - a[i - 1][1];
  47. if (j >= 1) dp[i][j][3] = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]),
  48. min(dp[i - 1][j - 1][2], dp[i - 1][j - 1][3]));
  49. }
  50. }
  51. int min_ans = 1e9, ind = 0;
  52. for (int i = 0; i < 4; i++) {
  53. if (min_ans > dp[n][k][i]) {
  54. min_ans = dp[n][k][i];
  55. ind = i;
  56. }
  57. }
  58. int nn = n, kk = k;
  59. vector<vector<int>> ans(n + 1, vector<int> (2, 0));
  60. while (nn > 0){
  61. if (ind == 0){
  62. nn -= 1;
  63. min_ans = min(min(dp[nn][kk][0], dp[nn][kk][1]), min(dp[nn][kk][2], dp[nn][kk][3]));
  64. if (min_ans == dp[nn][kk][0]) ind = 0;
  65. if (min_ans == dp[nn][kk][1]) ind = 1;
  66. if (min_ans == dp[nn][kk][2]) ind = 2;
  67. if (min_ans == dp[nn][kk][3]) ind = 3;
  68. } else if (ind == 1){
  69. ans[nn][0] = kk;
  70. ans[nn - 1][0] = kk;
  71. nn -= 1;
  72. kk -= 1;
  73. min_ans = min(dp[nn][kk][0], dp[nn][kk][2]);
  74. if (min_ans == dp[nn][kk][0]) ind = 0;
  75. if (min_ans == dp[nn][kk][2]) ind = 2;
  76. } else if (ind == 2){
  77. ans[nn][1] = kk;
  78. ans[nn - 1][1] = kk;
  79. nn -= 1;
  80. kk -= 1;
  81. min_ans = min(dp[nn][kk][0], dp[nn][kk][1]);
  82. if (min_ans == dp[nn][kk][0]) ind = 0;
  83. if (min_ans == dp[nn][kk][1]) ind = 1;
  84. } else {
  85. ans[nn][0] = kk;
  86. ans[nn][1] = kk;
  87. nn -= 1;
  88. kk -= 1;
  89. min_ans = min(min(dp[nn][kk][0], dp[nn][kk][1]),
  90. min(dp[nn][kk][2], dp[nn][kk][3]));
  91. if (min_ans == dp[nn][kk][0]) ind = 0;
  92. if (min_ans == dp[nn][kk][1]) ind = 1;
  93. if (min_ans == dp[nn][kk][2]) ind = 2;
  94. if (min_ans == dp[nn][kk][3]) ind = 3;
  95. }
  96. }
  97. for (int i = 1; i <= n; i++){
  98. cout << ans[i][0] << " " << ans[i][1] << '\n';
  99. }
  100. cout.close();
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement