Submission #60081369

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
  const int maxn=2e5+5,maxstate=(1<<20)+5;
  int a[maxn],vec[23][maxn],cnt[23],f[maxstate];
  inline int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
      cin>>a[i];
      vec[a[i]][++cnt[a[i]]]=i;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<(1<<20);++i){
      for(int j=1;j<=20;++j){
        if(i&(1<<(j-1))){
          int tmp=f[i^(1<<(j-1))];
          int it=upper_bound(vec[j],vec[j]+cnt[j]+1,tmp)-vec[j];
          if(it+1<=cnt[j]){
            f[i]=min(f[i],vec[j][it+1]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
namespace SOLUTION{
	const int maxn=2e5+5,maxstate=(1<<20)+5;
	int a[maxn],vec[23][maxn],cnt[23],f[maxstate];
	inline int main(){
		int n;
		cin>>n;
		for(int i=1;i<=n;++i){
			cin>>a[i];
			vec[a[i]][++cnt[a[i]]]=i;
		}
		memset(f,0x3f,sizeof(f));
		f[0]=0;
		for(int i=1;i<(1<<20);++i){
			for(int j=1;j<=20;++j){
				if(i&(1<<(j-1))){
					int tmp=f[i^(1<<(j-1))];
					int it=upper_bound(vec[j],vec[j]+cnt[j]+1,tmp)-vec[j];
					if(it+1<=cnt[j]){
						f[i]=min(f[i],vec[j][it+1]);
					}
				}
			}
		}
		int ans=0;
		for(int i=0;i<(1<<20);++i){
			if(f[i]<=n){
				int cnt=0;
				for(int j=1;j<=20;++j){
					if(i&(1<<(j-1))){
						++cnt;
					}
				}
				ans=max(ans,cnt);
			}
		}
		cout<<(ans<<1)<<"\n";
		return 0;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	SOLUTION::main();
	return 0;
}
/*
12
1 1 2 2 3 3 20 20 19 19 18 18
*/

Submission Info

Judge Result