fork(3) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MOD = 1e9;
  6.  
  7. vector<int> sum;
  8.  
  9. void add(int pos, int k)
  10. {
  11. for(; pos < sum.size(); pos |= pos + 1)
  12. sum[pos] = (sum[pos] + k) % MOD;
  13. }
  14.  
  15. int get(int pos)
  16. {
  17. int ret = 0;
  18. for(; pos > 0; pos = (pos & (pos + 1)) - 1)
  19. ret = (ret + sum[pos]) % MOD;
  20. return ret;
  21. }
  22.  
  23. int main()
  24. {
  25. int n, k;
  26. cin >> n >> k;
  27. vector<int> a(n), b(n, 1);
  28. for(int i = 0; i < n; i++)
  29. cin >> a[i];
  30. for(int i = 0; i < k; i++)
  31. {
  32. sum.assign(n + 1, 0);
  33. for(int j = n - 1; j >= 0; j--)
  34. {
  35. add(a[j], b[j]);
  36. b[j] = get(a[j] - 1);
  37. }
  38. }
  39. cout << get(n);
  40. return 0;
  41. }
Runtime error #stdin #stdout #stderr 0s 3428KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc