fork(105) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define f first
  5. #define s second
  6.  
  7. int main() {
  8. ll n,k;
  9. cin>>n>>k;
  10.  
  11. ll arr[n];
  12. for(int i=0;i<n;i++) cin>>arr[i];
  13.  
  14. vector<vector<ll>> dp(n,vector<ll> (k+1,1));
  15. //intialised to 1 keeping in viewing that seq has len==1 now
  16.  
  17. map<pair<ll,ll>,ll> m;
  18. set<pair<ll,ll>> seta[k+1];
  19.  
  20.  
  21. for(ll i=0;i<n;i++)
  22. {
  23. for(ll j=0;j<=k;j++)
  24. {
  25. // for(int p=0;p<i;p++)
  26. // {
  27. // ll a=-1,b=-1; if(arr[i]==arr[p]) a=dp[p][j]+1; else if(j>=1) b=dp[p][j-1]+1;
  28.  
  29. // dp[i][j]=max({dp[i][j],a,b});
  30. // }
  31.  
  32. ll a=-1,b=-1;
  33.  
  34. a=m[{arr[i],j}]+1;
  35.  
  36. ll val=-2;
  37.  
  38. //seta[j]
  39. if(j>=1 && !seta[j-1].empty())
  40. {
  41. auto e1=prev(seta[j-1].end());
  42. if((*e1).s==arr[i])
  43. {
  44. if(e1!=seta[j-1].begin()) {e1=prev(e1);val=(*e1).f;}
  45.  
  46. }
  47. else val=(*e1).f;
  48. }
  49.  
  50.  
  51. if(j>=1) b=val+1;
  52.  
  53. dp[i][j]=max({dp[i][j],a,b});
  54.  
  55. if(seta[j].find({m[{arr[i],j}],arr[i]})!=seta[j].end())
  56. {
  57. seta[j].erase({m[{arr[i],j}],arr[i]});
  58. }
  59.  
  60. m[{arr[i],j}]=max(m[{arr[i],j}],dp[i][j]);
  61. seta[j].insert({m[{arr[i],j}],arr[i]});
  62.  
  63. }
  64.  
  65.  
  66. }
  67.  
  68. cout<<dp[n-1][k]<<endl;
  69. }
  70.  
Runtime error #stdin #stdout 0.01s 5528KB
stdin
Standard input is empty
stdout
Standard output is empty