Submission #880253

#	Time	Username	Problem	Language	Result	Execution time	Memory
880253		yusuf12360	Sequence (APIO23_sequence)	C++17	11 / 100	2086 ms	52728 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
int sequence(int n, vector<int> a) {
	vector<vector<int>> pos(n+1);
	for(int i=0; i<n; i++) pos[a[i]].push_back(i);
	int ans=0;
	for(int i=1; i<=n; i++) {
		for(int p : pos[i]) {
			int temp=0, els=0, add=0;
			set<int> s; s.insert(0);
			for(int l=p-1; l>=0; l--) {
				if(a[l]==i) break;
				else if(a[l]<i) add--;
				else add++;
				s.insert(add);
			}
			for(int r=p; r<n; r++) {
				if(a[r]==i) {
					temp++;
					if(abs(els)<=temp) ans=max(ans, temp);
					else {
						auto it=s.lower_bound(-temp-els);
						if(it!=s.end() && abs(els+*it)<=temp) ans=max(ans, temp);
					}
				} else if(a[r]<i) els--;
				else els++;
			}
		}
	}
	return ans;
}

• 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