fork(1) download
copy 
  1. /* 
  2. Task: 1462E2
  3. Date: Dec 18 2020
  4. Written by aLittleLove (Minh Vu)
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define rep(i,n) for (int i=0, _n=n; i<_n; i++)
  9. #define FOR(i,a,b) for (int _a=(a), _b=(b), i=_a; _a<=_b?i<=_b:i>=_b; _a<=_b?i++:i--)
  10. #define _mem(a, b) memset(a, (b), sizeof(a))
  11. #define pb push_back
  12. #define fi first
  13. #define se second
  14. #define sz(a) int((a).size())
  15.  
  16. using namespace std;
  17. typedef long long ll;
  18. typedef int64_t i64;
  19. typedef pair<int, int> pii;
  20. typedef vector<pii> vii;
  21. typedef vector<int> vi;
  22. const int N = 2e5 + 5;
  23. const int inf = 1e9;
  24. const i64 mod = 1e9 + 7;
  25. const double pi = atan(1) * 4.0;
  26. template<typename T, typename U> inline void mini(T &x, U y) { if(y < x) x = y; }
  27. template<typename T, typename U> inline void maxi(T &x, U y) { if(x < y) x = y; }
  28.  
  29. i64 _pow(i64 x, i64 y)
  30. {
  31.     if (y==0) return 1;
  32.     i64 tmp = _pow(x, y/2ll);
  33.     if (y&1) return (tmp%mod * tmp%mod * x%mod)%mod;
  34.     return (tmp%mod * tmp%mod)%mod;
  35. }
  36.  
  37. int a[N];
  38. i64 fact[N], invFact[N];
  39.  
  40. i64 C(int n, int k)
  41. {
  42.     if (k>n) return 0;
  43.     return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
  44. }
  45.  
  46. void Solve()
  47. {
  48.     int n, m, k;
  49.     i64 ans = 0;
  50.     cin >> n >> m >> k;
  51.     rep(i,n) cin >> a[i];
  52.     sort(a, a+n);
  53.     for (int i=0; i<n; i++)
  54.     {
  55.         int l = i + 1;
  56.         int r = upper_bound(a,a+n,a[i]+k) - a;
  57.         ans = (ans + C(r - l, m - 1))%mod;
  58.     }
  59.     cout << ans << '\n';
  60. }
  61.  
  62. int main()
  63. {
  64.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  65.     //freopen("input.txt","r",stdin);
  66.     int nTest; cin >> nTest;
  67.     fact[0] = invFact[0] = 1;
  68.     for (int i=1; i<N; i++)
  69.     {
  70.         fact[i] = (fact[i - 1] * i) % mod;
  71.         invFact[i] = _pow(fact[i], mod - 2);
  72.     }
  73.     while (nTest--) Solve();
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0.08s 6872KB
comments (?)
stdin
copy 
4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4
stdout
copy 
2
6
1
20
https://ideone.com/1ssMV0
Codeforces 1462E2
language:
C++14 (gcc 8.3)
created:
4 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!