Submission #891690

#TimeUsernameProblemLanguageResultExecution timeMemory
891690ind1vDifference (POI11_roz)C++11
70 / 100
620 ms16168 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int n; int f[N], g[N]; vector<int> idx[26]; int ans = 0; int b[N]; int ptr; void solve(int mn, int mx) { ptr = 1; int i = 0, j = 0; while (i < (int) idx[mn].size() && j < (int) idx[mx].size()) { if (idx[mn][i] < idx[mx][j]) { b[ptr] = -1; ptr++; i++; } else if (idx[mx][j] < idx[mn][i]) { b[ptr] = 1; ptr++; j++; } } while (i < (int) idx[mn].size()) { b[ptr] = -1; ptr++; i++; } while (j < (int) idx[mx].size()) { b[ptr] = 1; ptr++; j++; } int sum = 0; for (int i = 1; i <= ptr; i++) { sum = max(b[i], b[i] + sum); f[i] = sum; } sum = 0; for (int i = ptr; i >= 1; i--) { sum = max(b[i], b[i] + sum); g[i] = sum; } for (int i = 1; i <= ptr; i++) { if (b[i] == -1) { ans = max(ans, f[i] + g[i] + 1); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { char d; cin >> d; idx[d - 'a'].push_back(i); } for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { if (i != j && !idx[i].empty() && !idx[j].empty()) { solve(i, j); } } } cout << ans << '\n'; return 0; }
#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...