fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define C make_pair
  3. #define ll long long
  4. #define all(a) a.begin(),a.end()
  5. #define name "task"
  6. #define ln "\n"
  7. using namespace std;
  8.  
  9. int n,k;
  10. map<int,int> pos,vt;
  11. const int maxN=5*1e5+9;
  12. int a[maxN],b[maxN];
  13. vector<int> ans;
  14. int len=1;
  15. void inp(){
  16. 	cin>>n>>k;
  17. }
  18. void solve_if_k_equal_1(){
  19. 	for(int i=0;i<n;++i){
  20. 		cin>>a[i];
  21. 		pos[a[i]]=i;
  22. 	}
  23. 	for(int i=0;i<n;++i){
  24. 		cin>>b[i];
  25. 		vt[i]=pos[b[i]];
  26. 	}
  27. 	for(int i=0;i<n;++i){
  28. 		auto it=lower_bound(ans.begin(),ans.end(),vt[i]);
  29.         if(it!=ans.end()) *it=vt[i];
  30.         else ans.push_back(vt[i]);
  31. 	}
  32. 	cout<<ans.size();
  33. }
  34. void solve_if_n_less_than_1e3(){
  35. 	n*=k;
  36. 	for(int i=0;i<n;++i)
  37. 		cin>>a[i];
  38. 	for(int i=0;i<n;++i)
  39. 		cin>>b[i];
  40. 	ll dp[n+9][n+9];
  41. 	memset(dp,0,sizeof(dp));
  42. 	for(int i=1;i<=n;++i){
  43. 		for(int j=1;j<=n;++j){
  44. 			if(a[i-1]==b[j-1])
  45. 				dp[i][j]=dp[i-1][j-1]+1;
  46. 			else{
  47. 				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  48. 			}
  49. 		}
  50. 	}
  51. 	cout<<dp[n][n];
  52. }
  53. int main(){
  54.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  55.     if(fopen(name".inp","r")){
  56.         freopen(name".inp","r",stdin);
  57.         freopen(name".out","w",stdout);
  58.     }
  59.     inp();
  60.     if(k==1){
  61.     	solve_if_k_equal_1();
  62.     } else{
  63.     	solve_if_n_less_than_1e3();
  64.     }
  65. }
  66.  
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin
copy 
3 2
1 2 3 1 2 3
2 1 3 3 2 1
stdout
copy 
3
https://ideone.com/515chY
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!