Submission #1200378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200378		crispxx	Sequence (APIO23_sequence)	C++20	12 / 100	85 ms	10064 KiB

sequence

#include "sequence.h"

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

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

int sequence(int n, std::vector<int> a) {
	int cnt1 = count(all(a), 1);
	int cnt2 = count(all(a), 3);
	
	if(cnt1 >= (n + 1) / 2 || cnt2 >= (n + 1) / 2) {
		return max(cnt1, cnt2);
	}
	
	int ans = count(all(a), 2);
	
	auto solve = [&](int x) {
		vector<int> cnt(n + 1), sum(n + 1), mn(n + 1);
		
		for(int i = 0; i < n; i++) {
			cnt[i + 1] = cnt[i] + (x == a[i]);
			sum[i + 1] = sum[i] + (x == a[i] ? 1 : -1);
			mn[i + 1] = min(mn[i], sum[i + 1]);
		}
		
		for(int i = 0; i <= n; i++) mn[i] = -mn[i];
		
		int res = 0;
		
		for(int r = 0; r <= n; r++) {
			int l = lower_bound(all(mn), -sum[r]) - mn.begin();
			if(l <= r) {
				res = max(res, cnt[r] - (l > 0 ? cnt[l - 1] : 0));
			}
		}
		
		return res;
	};
	
	return max({ans, solve(1), solve(3)});
}

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