Submission #1093188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093188		alexander707070	Sequence (APIO23_sequence)	C++17	11 / 100	2058 ms	15448 KiB

sequence

#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

int n,a[MAXN],ans,c[MAXN];
int pref[MAXN],mins[MAXN],maxs[MAXN];

int solve(int val){
	for(int i=1;i<=n;i++){
		pref[i]=mins[i]=maxs[i]=0;

		if(a[i]<val)mins[i]=1;
		if(a[i]>val)maxs[i]=1;
		if(a[i]==val)pref[i]=1;
	}

	for(int i=1;i<=n;i++){
		pref[i]+=pref[i-1]; mins[i]+=mins[i-1]; maxs[i]+=maxs[i-1];
	}

	int res=0;
	for(int i=1;i<=n;i++){
		for(int f=i;f<=n;f++){
			if(pref[f]-pref[i-1]>=abs( maxs[f]-maxs[i-1] - (mins[f]-mins[i-1]) ))res=max(res,pref[f]-pref[i-1]);
		}
	}

	return res;
}

int sequence(int N, std::vector<int> A){
	n=N;
	for(int i=1;i<=n;i++){
		a[i]=A[i-1];
	}

	for(int i=1;i<=n;i++){
		ans=max(ans,solve(i));
	}

	return ans;
}

/*int main(){

	cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1})<<"\n";
	cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2})<<"\n";
	
	return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18