Nson Nson - 1 year ago 65
C++ Question

(c++) How to effectively make ascending sequences (dyn. solution)

I am currently trying to make a program which involves ascending sequences. N is for the size of the sequence and K is the maximum number, for example

Input: 2,3

Output: 6 (1,1 - 1,2 - 1,3 - 2,2 - 2,3 - 3,3)

My current code outputs the right answer however it takes way too much time to get to the right answer. What is the fastest solution of this and how do I do the dynamical solution? Here is the code with the slow solution :

using namespace std;
int n,k,cnt=0,mod=1000000007;
int seq(int n, int k, int first, int depth){
if(depth > n){
cnt = cnt + 1;
return cnt;
else {
for(int i=first;i<=k;i++){
return cnt;
int main()
return 0;

Answer Source

I have solved this problem using dynamic programming.

    #define up(j,k,i) for(i=j;i<k;i++)
    #define down(j,k,i) for(i=j;i>k;i--)
    #define pp(n) printf("%lld\n",n)
    #define is(n) scanf("%lld",&n)
    #define ips(n) scanf("%lld",n)
    #define ss(s) scanf("%s",s)
    #define cool 0
    #define pb push_back
    #define mp make_pair
    #define F first
    #define S second
    #define f(i) cout<<i<<endl;
    #define pll pair<lld,lld> 
    #define pi acos(-1)
    #define ds(n,m) scanf("%lld %lld",&n,&m)
    #define ts(n,m,k) scanf("%lld %lld %lld",&n,&m,&k)
    typedef long double ld;
    typedef long long int lld;
    using namespace std;
    const lld M =1e3+7;
    const lld mod=1e9+7;
    const lld infi =LLONG_MAX;
    lld i,j,ans,k,n,x,y,m,mymax=LLONG_MIN,mymin=LLONG_MAX,b,c,z,sum;
    lld dp[M][M],s[M][M];
    int main()
      lld n,k;


            return 0;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download