Submission #1002160

#TimeUsernameProblemLanguageResultExecution timeMemory
1002160votranngocvyDifference (POI11_roz)C++14
100 / 100
658 ms22100 KiB
#include <bits/stdc++.h> using namespace std; #define NAME "task" const int N = 1e6 + 5; const int inf = 0x3f3f3f3f; vector<int>pos[30]; int n,ans,cnt[N],pre[N]; char s[N]; void calc(int a,int b) { vector<int>vec; int i = 0,j = 0; while (i < (int)pos[a].size() && j < (int)pos[b].size()) { if (pos[a][i] < pos[b][j]) { vec.push_back(1); i++; } else { vec.push_back(-1); j++; } } while (i < (int)pos[a].size()) { vec.push_back(1); i++; } while (j < (int)pos[b].size()) { vec.push_back(-1); j++; } int m = vec.size(); pre[0] = 0,cnt[0] = 0; for (int i = 1; i <= m; i++) { if (vec[i - 1] == -1) cnt[i] = cnt[i - 1] + 1; else cnt[i] = cnt[i - 1]; pre[i] = pre[i - 1] + vec[i - 1]; } int Min = inf; j = 0; for (int i = 1; i <= m; i++) { while (j < i && cnt[i] - cnt[j] > 0) { Min = min(Min,pre[j]); j++; } ans = max(ans,pre[i] - Min); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> s[i]; pos[s[i] - 'a'].push_back(i); } for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) if (i != j && pos[i].size() && pos[j].size()) calc(i,j); cout << ans << "\n"; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...