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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/DWEZcW
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!