fork download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <math.h>
  5. #include <cmath>
  6. #include <unordered_map>
  7. #include <map>
  8. #include <deque>
  9. #include <cstdio>
  10. #include <stdio.h>
  11.  
  12. using namespace std;
  13. typedef long long ll;
  14. const int maxD = 1e5 + 2;
  15. ll prefv[maxD], sel[maxD];
  16. pair<int, int> xv[maxD];
  17.  
  18. int main()
  19. {
  20. int t;
  21. cin >> t;
  22. for(int i = 1; i <= t; ++i)
  23. {
  24. int n, R, k;
  25. ll ans = 0;
  26. int mini = 1e9;
  27. cin >> n >> R >> k;
  28. for(int j = 0; j < n; ++j)
  29. {
  30. int x, v;
  31. cin >> x >> v;
  32. xv[j] = make_pair(x, v);
  33. mini = min(x, mini);
  34. prefv[j] = 0;
  35. sel[j] = -1;
  36. }
  37. sort(xv, xv + n);
  38. prefv[0] = xv[0].second;
  39. for(int j = 1; j < n; ++j) prefv[j] += prefv[j - 1] + xv[j].second;
  40. for(int j = 0; j < k; ++j)
  41. {
  42. int l, r, curl;
  43. ll best;
  44. pair<int, int> bestcur;
  45. l = r = best = curl = 0;
  46. for(int m = 0; m < n; ++m)
  47. {
  48. if( sel[m] != -1 )
  49. {
  50. m = sel[m];
  51. curl = m;
  52. continue;
  53. }
  54.  
  55. l = curl;
  56. r = m;
  57. if( xv[m].first - mini <= R * 2 )
  58. {
  59. if( prefv[m] >= best ) {
  60. best = prefv[m];
  61. bestcur = make_pair(m, 0);
  62. continue;
  63. }
  64. }
  65.  
  66. while(l + 1 < r)
  67. {
  68. int mid = (l + r) >> 1;
  69. if( xv[m].first - xv[mid + 1].first <= R * 2 ) r = mid;
  70. else l = mid;
  71. }
  72.  
  73. if( xv[m].first - xv[l + 1].first <= R * 2 ) r = l;
  74.  
  75. if( prefv[m] - prefv[r] >= best )
  76. {
  77. best = prefv[m] - prefv[r];
  78. bestcur = make_pair(m, r + 1);
  79. }
  80. }
  81.  
  82. ans += best;
  83. if( best )
  84. sel[bestcur.second] = bestcur.first;
  85. }
  86. cout << "Case " << i << ": " << ans << '\n';
  87. }
  88.  
  89. return 0;
  90. }
Success #stdin #stdout 0s 18408KB
stdin
Standard input is empty
stdout
Case 1: 0
Case 2: 0