Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include "optimization.h"
  4.  
  5. using namespace std;
  6.  
  7. #define INFILE "input.txt"
  8. #define OUTFILE "output.txt"
  9.  
  10. void Partition(int l, int r, pair<int, int> x, vector<pair<int, int>> & a, int& i, int& j) {
  11. vector<pair<int, int>> lss;
  12. vector<pair<int, int>> mid;
  13. vector<pair<int, int>> more;
  14. for (int i = l; i < r; ++i) {
  15. if (a[i].second == x.second) {
  16. mid.push_back(a[i]);
  17. } else
  18. if (a[i].second < x.second) {
  19. lss.push_back(a[i]);
  20. } else {
  21. more.push_back(a[i]);
  22. }
  23. }
  24. int index = l;
  25. for (; index - l < lss.size(); ++index) {
  26. a[index] = lss[index - l];
  27. }
  28. j = index;
  29. for (; index - l < mid.size() + lss.size(); ++index) {
  30. a[index] = mid[index - lss.size() - l];
  31. }
  32. i = index;
  33. for (; index - l < more.size() + lss.size() + mid.size(); ++index) {
  34. a[index] = more[index - l - mid.size() - lss.size()];
  35. }
  36. }
  37.  
  38. int Stat(int64_t k, int l, int r, vector<pair<int, int>> & a) {
  39. if (r - l < 1) return 0;
  40. if (r - l == 1) return a[l].second;
  41. int i = l, j = r;
  42. int pivot = l + (r - l) / 2;
  43. Partition(l, r, a[pivot], a, i, j);
  44. int64_t sum = 0;
  45.  
  46. for (int t = 0; t < j; ++t) {
  47. sum += a[t].first;
  48. }
  49.  
  50. int64_t sumd = sum;
  51. for (int t = j; t < i; t++)
  52. {
  53. sumd += a[t].first;
  54. }
  55.  
  56. if (2 * sum > k && j - l > 0) {
  57. return Stat(k, l, j, a);
  58. } else
  59. if (2 * sumd > k){
  60. return a[j].second;
  61. } else {
  62. return Stat(k, i, r, a);
  63. }
  64. }
  65.  
  66. int main() {
  67. freopen (INFILE, "r", stdin);
  68. freopen (OUTFILE, "w", stdout);
  69.  
  70. unsigned int t, n;
  71. unsigned int halfN;
  72. t = readInt();
  73. for (int i = t; i > 0; --i) {
  74. n = readInt();
  75. vector<pair<int, int>> Z;
  76. vector<pair<int, int>> T;
  77.  
  78. vector<int> weights;
  79. vector<int> xs;
  80. vector<int> ys;
  81. int64_t half_weight = 0;
  82. for (int j = 0; j < n; ++j) {
  83. int x = readInt();
  84. int y = readInt();
  85. int w = readInt();
  86. xs.push_back(x);
  87. ys.push_back(y);
  88. weights.push_back(w);
  89. half_weight += w;
  90. Z.push_back(make_pair(w, x + y));
  91. T.push_back(make_pair(w, x - y));
  92. }
  93.  
  94. int z_index = Stat(half_weight, 0, n, Z);
  95. int t_index = Stat(half_weight, 0, n, T);
  96.  
  97. int X = (z_index + t_index);
  98. int Y = (z_index - t_index);
  99.  
  100. int64_t sum_time = 0;
  101. for (int k = 0; k < n; ++k) {
  102. sum_time += weights[k] * max(abs(2 * xs[k] - X), abs(2 * ys[k] - Y));
  103. }
  104.  
  105. writeInt(sum_time, '\n');
  106. }
  107.  
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement