CF: 323-Div1 B ( Matrix Expo )

CF: 323-Div1 B ( Matrix Expo )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     500002
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

#define N 102
int ms;///Matrix Size GLOBAL: N
struct mat {
    ll m[N][N];
    mat() {};
    void Nullify( ) {
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                m[i][j]=0;
            }
        }
    }
    void Unify( ) {
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                if(i==j)m[i][j]=0; ///fOR THIS CASE
                else m[i][j]=0;
            }
        }
    }
    mat operator *(const mat &b )const {
        mat c;
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                c.m[i][j]=-inf;
                for(int k=0; k<ms; k++) {
                    c.m[i][j]=max( c.m[i][j], m[i][k]+b.m[k][j] );///FOR THIS PROB
                }
            }
        }
        return c;
    }
    mat Pow(int p) {
        mat ret;
        ret.Unify();
        mat B=(*this);
        while(p) {
            if(p & 1)ret = (ret * B);
            B = (B * B);
            p>>=1;
        }
        return ret;
    }
    void Print( ) {
        cout<<endl;
        cout<< "Matix is:\n";
        cout<< "****************************\n";
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                cout<<m[i][j]<< "  ";
            }
            cout<<endl;
        }
        cout<< "****************************\n";
        cout<<endl;
    }
} b;


int ar[103];
int main() {
    int n,t,i,j;
    S2(n,t);
    ms=n; ///MatSize Global Var;
    fr(i,0,n-1)S(ar[i]);
    for(int i=0; i<n; i++) { ///Last Lefted Idx;
        for(int j=0; j<n; j++) { ///Now To-End Idx
            if( ar[j]>=ar[i] ) {
                b.m[i][j]=1;
                for(int k=0; k<j; k++) { ///LIS from LastIdx based NowEnd Idx.
                    if( ar[k]>=ar[i] && ar[k]<=ar[j] )
                        b.m[i][j]=max( b.m[i][j],b.m[i][k]+1 );
                }
            } else b.m[i][j]=-inf;
        }
    }
    mat ret=b.Pow(t);
    ll mx=1;
    fr(i,0,ms-1) {
        fr(j,0,ms-1) {
            mx=max(mx,ret.m[i][j]);
        }
    }
    printf("%lld\n",mx);

    return 0;
}