이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
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;
vector<pii>vec;
for (auto x: pos[a]) vec.push_back(mp(x,1));
for (auto x: pos[b]) vec.push_back(mp(x,-1));
int m = vec.size();
sort(vec.begin(),vec.end());
maxPreSum[0] = maxSufSum[m + 1] = 0;
int sum = 0;
for (int i = 1; i <= m; i++) {
sum = max(sum + vec[i - 1].se,vec[i - 1].se);
maxPreSum[i] = sum;
}
sum = 0;
for (int i = m; i > 0; i--) {
sum = max(sum + vec[i - 1].se,vec[i - 1].se);
maxSufSum[i] = sum;
}
int ans = 0;
for (int i = 1; i <= m; i++) {
if (vec[i - 1].se == 1) continue;
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 = 0; 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... |