fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 1e5 + 5;
  5. const int Mod = 1e9;
  6. int a[N + 5], n, k, f[15][N];
  7. void update(int k, int pos, int val){
  8.     while(pos <= n){
  9.         f[k][pos] = (f[k][pos] + val) % Mod;
  10.         pos += pos & -pos;
  11.     }
  12. }
  13. int get(int k, int pos){
  14.     int sum = 0;
  15.     while(pos > 0){
  16.         sum = (sum + f[k][pos]) % Mod;
  17.         pos -= pos & -pos;
  18.     }
  19.     return sum;
  20. }
  21. signed main(){
  22.     ios::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24.     cin >> n >> k;
  25.     for(int i = 1; i <= n; i++){
  26.         cin >> a[i];
  27.     }
  28.  
  29.     for(int i = 1; i <= n; i++){
  30.         update(1, a[i], 1);
  31.         for(int j = k; j >= 2; j--){
  32.             int cur = (get(j - 1, n) - get(j - 1, a[i]) + Mod) % Mod;
  33.             update(j, a[i], cur);
  34.         }
  35.     }
  36.  
  37.     cout << get(k, n);
  38. }
  39.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b0jV9s
language:
C++14 (gcc 8.3)
created:
2 days 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!