fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1e9 + 7;
  5. const int MAX_N = 25;
  6.  
  7. int N, K, A[MAX_N];
  8. int dp[1<<MAX_N];
  9.  
  10. int f(int L) {
  11.     if(dp[L]!=-1)
  12.         return dp[L];
  13.  
  14.     int num_seq = 0, highest_bit = -1, i;
  15.     for(int j=0; j<N; j++) {
  16.         if(L & 1<<j) {      // if j in L
  17.             num_seq++;
  18.             highest_bit = j;
  19.         }
  20.     }
  21.     i = highest_bit + 1;
  22.     if(i==N)
  23.         return 1;
  24.     dp[L] = 0;
  25.     for(int j=0; j<i; j++)
  26.         if(L & 1<<j)
  27.             if(A[i] < A[j])
  28.                 dp[L] = (dp[L] + f(L ^ 1<<j | 1<<i)) % MOD;
  29.                 // (L ^ 1<<j) removes j from L if already present
  30.                 // (L | 1<<i) adds i to L
  31.     if(num_seq<K)
  32.         dp[L] = (dp[L] + f(L | 1<<i)) % MOD;
  33.  
  34.     return dp[L];
  35. }
  36.  
  37. int main() {
  38.     cin >> N >> K;
  39.     for(int i=0; i<N; i++)
  40.         cin >> A[i];
  41.  
  42.     memset(dp, -1, sizeof(dp));
  43.     int ans = f(0);
  44.     cout << ans << endl;
  45.  
  46.     return 0;
  47. }
Success #stdin #stdout 0.03s 147136KB
comments (?)
stdin
copy 
5 2
6 2 4 1 1
stdout
copy 
4
https://ideone.com/mby8D5
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!