# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1178425 | Agageldi | Sequence (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "sequence.h"
#include "grader.cpp"
using namespace std;
#define MAX_N 5000005
#define ll long long
#define SZ(v) (int)v.size()
ll a[MAX_N], n, ans, jogap = -1, tr = 0;
vector <int> v;
int sequence(int N, vector<int> A) {
for(int i = 0;i < N; i++) {
a[A[i]]++;
if(a[A[i]] >= N / 2 + 1) jogap = a[A[i]];
if(i > 0 && A[i] < A[i - 1]) tr = 1;
}
if(~jogap) return jogap;
if(!tr) {
int p = 0, cnt = 0;
for(int i = 0; i < N - 1; i++){
if(A[i] != A[i + 1]) {
cnt = max(p + 1, cnt);
p = 0;
continue;
}
p++;
}
return max(cnt, p + 1);
}
memset(a,0,sizeof a);
for(int i = 0; i < N; i++) {
v.clear();
for(int j = i; j < N; j++) {
a[A[j]]++;
v.push_back(A[j]);
int ind = SZ(v) - 1;
while(ind > 0 && v[ind] < v[ind - 1]) {
swap(v[ind], v[ind - 1]);
ind--;
}
int med = (SZ(v) / 2);
ans = max({ans,a[v[med]],a[v[med - ((j - i + 1) % 2 == 0)]]});
}
for(int j = i; j < N; j++) {
a[A[j]]--;
}
}
return ans;
}