fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. signed main() {
  7. ios::sync_with_stdio(false);
  8. cin.tie(nullptr);
  9.  
  10. int n, k, x;
  11. cin >> n >> k >> x;
  12.  
  13. vector<int> a(n + 1);
  14. for (int i = 1; i <= n; i++)
  15. cin >> a[i];
  16.  
  17. sort(a.begin() + 1, a.end());
  18.  
  19. // r[i]: vị trí xa nhất có thể chọn nếu bắt đầu từ i
  20. vector<int> r(n + 2);
  21. int j = 1;
  22. for (int i = 1; i <= n; i++) {
  23. while (j <= n && a[j] - a[i] <= x)
  24. j++;
  25. r[i] = j - 1;
  26. }
  27.  
  28. // dp[j] = kết quả khi xét từ i+1
  29. // newdp[j] = kết quả khi xét từ i
  30. vector<int> dp(k + 1, 0), newdp(k + 1, 0);
  31.  
  32. for (int i = n; i >= 1; i--) {
  33. for (int jteam = 0; jteam <= k; jteam++) {
  34. // Không chọn i
  35. newdp[jteam] = dp[jteam];
  36.  
  37. // Chọn team bắt đầu tại i
  38. if (jteam > 0) {
  39. int len = r[i] - i + 1;
  40. newdp[jteam] = max(newdp[jteam],
  41. len + dp[jteam - 1]);
  42. }
  43. }
  44. dp = newdp;
  45. }
  46.  
  47. cout << dp[k] << "\n";
  48. }
Success #stdin #stdout 0.01s 5316KB
stdin
5 2 5
1 2 15 15 15
stdout
5