Problem Description

Given an integer array bi with a length of n, please tell me how many exactly different increasing subsequences.

P.S. A subsequence bai(1≤i≤k) is an increasing subsequence of sequence bi(1≤i≤n) if and only if 1≤a1<a2<...<ak≤n and ba1<ba2<...<bak.
Two sequences ai and bi is exactly different if and only if there exist at least one i and ai≠bi.

 

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,k(1≤n≤100,1≤k≤n)

Then follows n integers ai(0≤ai≤109)

 

Output

For each cases, please output an integer in a line as the answer.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

hujie

 

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<vector>

 6 #include<queue>

 7 #include<cstdio>

 8 #include<string.h>

 9 typedef long long ll;

10 using namespace std;

11 ll a[100005];

12 ll b[100005];

13

14 int main(void)

15 {

16     ll n,i,j,k,p,q;

17

18     while(scanf("%lld",&n)!=EOF)

19     { ll tt=0;

20         for(i=0; i<n; i++)

21         {

22             scanf("%lld",&a[i]);

23             tt+=a[i];

24         }

25         for(i=0; i<n; i++)

26         {

27             b[i]=(1890*a[i]+143)%10007-a[i];

28         }

29         ll sum=0;

30         ll cnt=b[0];

31         if(sum<cnt)

32         {

33             sum=cnt;

34         }

35         for(i=1; i<n; i++)

36         {

37             if(b[i-1]>=0)

38             {

39                 b[i]+=b[i-1];

40

41             }

42             if(sum<b[i])

43             {

44                 sum=b[i];

45             }

46         }

47         if(sum<0)

48         {

49             sum=0;

50         }

51         printf("%d\n",sum+tt);

52     }

53     return 0;

54

55

56 }