Submission #749893

#	Time	Username	Problem	Language	Result	Execution time	Memory
749893		Cyber_Wolf	Sequence (APIO23_sequence)	C++17	7 / 100	447 ms	53124 KiB

sequence

#include "sequence.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
#include <vector>
#define lg long long
using namespace std;

const lg N = 2e3+5;

int sequence(int nO, vector<int> a) 
{
	lg ans = 1;
	map<lg, lg> inc, dec;
	bool flag = true;
	vector<int> v = a;
	sort(v.begin(), v.end());
	for(int i = 0; i < nO; i++)
	{
		if(flag)	inc[a[i]]++;
		else	dec[a[i]]++;
		if(i && a[i] < a[i-1])
		{
			flag = false;
		}
	}
	for(auto it : inc)
	{
		auto it2 = lower_bound(v.begin(), v.end(), it.first)-v.begin();
		if(it2 >= nO/2)
		{
			// cout << it.first << ' ' << it2 << '\n';
			ans = max(ans, it.second+dec[it.first]);
		}
		ans = max(ans, it.second);
	}
	for(auto it : dec)
	{
		auto it2 = lower_bound(v.begin(), v.end(), it.first)-v.begin();
		if(it2 >= nO/2)
		{
			// cout << it.first << '\n';
			ans = max(ans, it.second+inc[it.first]);
		}
		ans = max(ans, it.second);
	}
	
  return ans;
}
/*
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

9
1 1 2 3 4 3 2 1 1


7
1 2 3 1 2 1 3
*/

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