CodeForces #634 Div 3 E2

1 
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 2e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif

    ll t;
    cin >> t;

    while(t--)
    {
        map<ll,ll> cnt;

        ll n;
        cin >> n;
        vector<ll> v(n+1);

        for(ll i=1 ; i<=n ; ++i) 
        {
            cin >> v[i];
            cnt[v[i]]++;
        }

        ll ans = 0;
        for(auto x : cnt)
        {
            for(auto y : cnt)
            {
                if( x.first == y.first )
                {
                    ans = max(ans, y.second);
                }
                else
                {
                    ll begin = 1, end = n , side_cnt=0 , center_cnt = y.second;
                    ans = max(ans , center_cnt);
                    while(begin < end)
                    {
                        while(begin < end && v[begin]!=x.first)  
                            {
                                if(v[begin] == y.first) center_cnt--; 
                                begin++;
                            }
                        while(begin < end && v[end]!=x.first) 
                            {
                                if(v[end] == y.first) center_cnt--; 
                                end--;
                            }
                         
                        if(begin >= end) break;
                          
                        side_cnt++;
                        ans = max(ans , center_cnt + 2*side_cnt);
                        begin++,end--;  
                    }
                }
            }
        }     

        cout << ans << endl;
    }

    return 0;
}

This gives TLE. How do I further reduce the time complexity?

2

Try Using array to store frequency instead of map.
I used array And Try optimizing Complexity to 200 * n because you are writing code of 200*(200)*n which will give TLE

3

Fod diye beta tum to

4

Can you share your code please?

5 
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d",&a)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%ld\n",a)
#define pll(a) printf("%lld\n",a) 
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",a)
#define ll long long
#define mod 1000000007
#define w while
#define pb push_back
#define mp make_pair

#define INF INT_MAX
#define fr(i,a,b) for(int i=a;i<=b;i++)

///////////////////////////////////////////////////////////////
int fre[201],fre1[201];
int cn[201][200005];
int main()
{
    int t;
    si(t);
    w(t--)
    {
    	int ans=0;
    	fr(i,0,200)
    	{
    		fre[i]=0;
    		fre1[i]=0;
    		cn[i][0]=0;
		}
        int n;
        cin>>n;
        int a[n+1];
        fr(i,1,n)
        {
        	cin>>a[i];
        	fre[a[i]]++;
        	fre1[a[i]]++;
        	ans=max(ans,fre[a[i]]);
        }
        fr(i,1,200)
        {
        	fr(j,1,n)
        	{
        		cn[i][j]=cn[i][j-1];
        		if(a[j]==i)
        		cn[i][j]++;
			}
		}
        fr(num,1,200)
        {
        	if(fre1[num]<=1)
        	continue;
        	fr(i,1,200)
        	fre[i]=fre1[i];
        	int st=1,end=n;
        	int cnt=0;
        	while(st<end)
        	{
        		while(a[st]!=num)
	        	{
	        		fre[a[st]]--;
	        		st++;
				}
				while(a[end]!=num)
				{
					fre[a[end]]--;
					end--;
				}
				st++;
				end--;
				cnt+=2;
				int mx=0;
				int temp=0;
				if(st<=end)
				{
					fr(j,1,200)
					{
						if(j!=num)
						temp=cn[j][end]-cn[j][st-1];
						mx=max(mx,temp);
					}
					ans=max(ans,mx+cnt);
				}
			}
        	
		}
		cout<<ans<<"\n";
    }
    return 0;
}