Advertisement
Guest User

Untitled

a guest
Jul 5th, 2019
2,096
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long double ld;
  4. typedef long long ll;
  5. const int mod = 998244353;
  6. int sum(int a, int b) {
  7. int s = (a + b);
  8. if (s >= mod) s -= mod;
  9. return s;
  10. }
  11. int sub(int a, int b) {
  12. int s = a - b;
  13. if (s < 0) s += mod;
  14. return s;
  15. }
  16. int mult(int a, int b) {
  17. return (1LL * a * b) % mod;
  18. }
  19. const int maxN = 1005;
  20. int a[maxN];
  21. int n, k;
  22. // a * (k - 1) > n
  23. int dp[maxN][maxN];
  24. int pref[maxN][maxN];
  25. int le[maxN];
  26. int solve(int val) {
  27. // all >= a
  28. for (int i = 0; i <= k; i++) {
  29. for (int j = 0; j <= n; j++) {
  30. dp[i][j] = 0;
  31. }
  32. }
  33. le[0] = 0;
  34. for (int i = 1; i <= n; i++) {
  35. le[i] = le[i - 1];
  36. while (a[i] - a[le[i] + 1] >= val) le[i]++;
  37. }
  38. dp[0][0] = 1;
  39. for (int i = 0; i + 1 <= k; i++) {
  40. pref[i][0] = dp[i][0];
  41. for (int j = 1; j <= n; j++) {
  42. pref[i][j] = sum(pref[i][j - 1], dp[i][j]);
  43. }
  44. for (int j = 1; j <= n; j++) {
  45. dp[i + 1][j] = pref[i][le[j]];
  46. }
  47. }
  48. int f = 0;
  49. for (int i = 1; i <= n; i++) f = sum(f, dp[k][i]);
  50. return f;
  51. }
  52. int main() {
  53. ios_base::sync_with_stdio(false);
  54. cin.tie(nullptr);
  55. //freopen("input.txt", "r", stdin);
  56. cin >> n >> k;
  57. for (int i = 1; i <= n; i++) {
  58. cin >> a[i];
  59. }
  60. sort(a + 1, a + n + 1);
  61. int ans = 0;
  62. for (int a = 1; a * (k - 1) <= 100000 + 10; a++) {
  63. ans = sum(ans, solve(a));
  64. }
  65. cout << ans;
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement