이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// fest
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
void FREOPEN() {
#ifdef COMP
freopen(".in", "r", stdin);
freopen("2.out", "w", stdout);
#endif
}
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }
const int N = 10500, M = 2, inf = 1e9 * 2, MOD = (int)1e9 + 7;
char CH[N];
const ll INF = 1e18;
const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};
const int P[] = {2019, 2017};
const int mod[] = {(int)1e9 + 3, (int)1e9 + 9};
map<pair<int, int>, int> cnt;
int h[M][N], pr[M][N];
int n;
pair<int, int> get(int l, int r) {
int f = ((h[0][r] - h[0][l - 1] + mod[0]) * 1ll * pr[0][n - l]) % mod[0];
int s = ((h[1][r] - h[1][l - 1] + mod[1]) * 1ll * pr[1][n - l]) % mod[1];
return {f, s};
}
void relax(ll &ans, int l, int r) {
cnt[get(l, r)]++;
ans = max(ans, cnt[get(l, r)] * 1ll * (r - l + 1));
}
int main() {
FREOPEN();
scanf("%s", CH);
string s = CH;
n = SZ(s);
for (int j = 0; j < M; j++) {
pr[j][0] = 1;
for (int i = 1; i <= n; i++) pr[j][i] = (pr[j][i - 1] * 1ll * P[j]) % mod[j];
for (int i = 1; i <= n; i++) h[j][i] = (h[j][i - 1] + (s[i - 1] * 1ll * pr[j][i])) % mod[j];
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
int sz = 1;
relax(ans, i, i);
while (i - sz >= 1 && i + sz <= n && s[i - sz - 1] == s[i + sz - 1]) {
relax(ans, i - sz, i + sz);
sz++;
}
sz = 1;
if (i == 1 || s[i - 1] != s[i - 2]) continue;
relax(ans, i - 1, i);
while (i - sz - 1 >= 1 && i + sz <= n && s[i - sz - 2] == s[i + sz - 1]) {
relax(ans, i - sz - 1, i + sz);
sz++;
}
}
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'int main()':
palindrome.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", CH);
^
# | 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... |