제출 #1200378

#제출 시각아이디문제언어결과실행 시간메모리
1200378crispxx서열 (APIO23_sequence)C++20
12 / 100
85 ms10064 KiB
#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)}); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...