Submission #2049779

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define MAX 123456

struct BIT{
  int t[MAX];
  void init(){
    for(int i=0;i<MAX;i++){
      t[i]=-1000000000;
    }
  }
  int maxm(int i=123450){
    int res=-1000000000;
    i+=5;
    while(i>0){
      res=max(res,t[i]);
      i-=(i&-i);
    }
    return res;
  }
  
  void update(int i,int x){
    i+=5;
    while(i<MAX){
      t[i]=max(t[i],x);
      i+=(i&-i);
    }
  }
};

BIT A[101];
int N,K;
int v[MAX];
vector<int> X;

void solve(){
  
  for(int i=0;i<N;i++){
    for(int j=0;j<=K;j++){
      int tmp=-1;
      if(j>0){
        tmp = A[j-1].maxm();
        A[j].update( v[i] , tmp+1);
      }

      int cost=-2;
      cost = A[j].maxm( v[i]-1 );

      if(i==0)cost=0;
      A[j].update( v[i], cost+1);

      //      cout<<max(tmp,cost+1)<<' ';
    }
    //    cout<<endl;
  }

  int ans=1;
  for(int i=0;i<=100;i++){
    ans=max(ans, A[i].maxm() );
  }
  cout<<ans<<endl;
}

int main(){
  cin>>N>>K;
  for(int i=0;i<N;i++){
    cin>>v[i];
    X.push_back(v[i]);
  }
  sort(X.begin(),X.end());
  X.erase( unique( X.begin(), X.end() ) , X.end() );
  
  for(int i=0;i<N;i++){
    v[i]=lower_bound( X.begin(),X.end(),v[i]) - X.begin();
    v[i]++;
    //    cout<<v[i]<<' ';
  }
  //  cout<<endl;
  solve();
  return 0;
}

Submission Info

Judge Result