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>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
using namespace std;
const int N = (int) 1000;
const int M = (int) 2e6 + 10;
const ll LINF = (ll) 1e18;
const int INF = (int) 1e9 + 7;
const double EPS = (double) 1e-9;
string st;
ll ans;
int lcp[N];
void solve_odd() {
vector<string> v;
for (int i = 0; i < sz(st); i++) {
int j = 0;
while (i - j >= 0 && i + j < sz(st) && st[i - j] == st[i + j]) j++;
v.pb(st.substr(i, j));
}
sort(all(v));
//for (auto it : v) cout << it << endl; cout << "-----\n";
for (int i = 0; i + 1 < sz(v); i++) {
lcp[i] = 0;
while (lcp[i] < min(sz(v[i]), sz(v[i + 1])) && v[i][lcp[i]] == v[i + 1][lcp[i]]) lcp[i]++;
}
for (int i = 0; i < sz(v); i++) {
int mn = lcp[i];
ans = max(ans, 2ll * sz(v[i]) - 1);
for (int j = i; j + 1 < sz(v); j++) {
mn = min(mn, lcp[j]);
ans = max(ans, (j - i + 2) * 1ll * (mn * 2 - 1));
}
}
}
void solve_even() {
vector<string> v;
for (int i = 0; i < sz(st); i++) {
int j = 0;
while (i - 1 - j >= 0 && i + j < sz(st) && st[i - 1 - j] == st[i + j]) j++;
v.pb(st.substr(i, j));
}
sort(all(v));
//for (auto it : v) cout << it << endl; cout << "-----\n";
for (int i = 0; i + 1 < sz(v); i++) {
lcp[i] = 0;
while (lcp[i] < min(sz(v[i]), sz(v[i + 1])) && v[i][lcp[i]] == v[i + 1][lcp[i]]) lcp[i]++;
}
for (int i = 0; i < sz(v); i++) {
int mn = lcp[i];
ans = max(ans, 2ll * sz(v[i]));
for (int j = i; j + 1 < sz(v); j++) {
mn = min(mn, lcp[j]);
ans = max(ans, (j - i + 2) * 2ll * mn);
}
}
}
int main() {
#define fn "balls"
#ifdef witch
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen(fn".in", "r", stdin);
// freopen(fn".out", "w", stdout);
#endif
cin >> st;
solve_odd();
solve_even();
cout << ans;
return 0;
}
# | 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... |