This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
char a[N];
vector<int>pos[30];
int n,val[N],maxPreSum[N],maxSufSum[N];
int calc(int a,int b) {
if (pos[a].size() == 0 || pos[b].size() == 0) return 0;
for (int i = 1; i <= n; i++) val[i] = 0;
for (auto x: pos[a]) val[x] = 1;
for (auto x: pos[b]) val[x] = -1;
maxPreSum[0] = maxSufSum[n + 1] = 0;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum = max(sum + val[i],val[i]);
maxPreSum[i] = sum;
}
sum = 0;
for (int i = n; i > 0; i--) {
sum = max(sum + val[i],val[i]);
maxSufSum[i] = sum;
}
int ans = 0;
for (auto i: pos[b]) {
int tmp = maxPreSum[i - 1] + maxSufSum[i + 1] - 1;
tmp = max(tmp,maxPreSum[i - 1] - 1);
tmp = max(tmp,maxSufSum[i - 1] - 1);
ans = max(ans,tmp);
}
for (auto x: pos[b]) val[x] = 1;
for (auto x: pos[a]) val[x] = -1;
maxPreSum[0] = maxSufSum[n + 1] = 0;
sum = 0;
for (int i = 1; i <= n; i++) {
sum = max(sum + val[i],val[i]);
maxPreSum[i] = sum;
}
sum = 0;
for (int i = n; i > 0; i--) {
sum = max(sum + val[i],val[i]);
maxSufSum[i] = sum;
}
for (auto i: pos[a]) {
int tmp = maxPreSum[i - 1] + maxSufSum[i + 1] - 1;
tmp = max(tmp,maxPreSum[i - 1] - 1);
tmp = max(tmp,maxSufSum[i - 1] - 1);
ans = max(ans,tmp);
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pos[a[i] - 'a'].push_back(i);
int ans = 0;
for (int i = 0; i < 26; i++)
for (int j = i + 1; j < 26; j++)
if (i != j) ans = max(ans,calc(i,j));
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |