fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 0
Case 2: 0
https://ideone.com/NkRObU
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!