結果
問題 | No.464 PPAP |
ユーザー |
![]() |
提出日時 | 2017-02-11 11:08:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,514 bytes |
コンパイル時間 | 1,601 ms |
コンパイル使用メモリ | 170,880 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-29 12:07:11 |
合計ジャッジ時間 | 2,706 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> std::vector<int> manachar(const std::string &s) { int n = s.size(); std::vector<int> rad(n); int c = 0; for (int r = 0; r < n; ++r) { int l = c - (r - c); if (r + rad[l] < c + rad[c]) { rad[r] = rad[l]; } else { int rr = c + rad[c]; int rl = r - (rr - r); while (rl >= 0 && rr < n && s[rl] == s[rr]) ++rr, --rl; rad[r] = rr - r; c = r; } } return rad; } std::string insert_dollar(const std::string &s){ int n = s.size(); std::string res(n*2 + 1, '$'); for(int i = 0; i < n; ++i){ res[i*2 + 1] = s[i]; } return res; } // [l, r) bool is_palindrome(int l, int r, const std::vector<int> &rad){ l = l*2 + 1; r = (r-1)*2 + 1; int c = (l + r) / 2; return r < c + rad[c]; } using namespace std; int main(){ string s; while(cin >> s){ int n = s.size(); auto rad = manachar(insert_dollar(s)); int pp[5010] = {}; for(int i = 1; i < n; ++i){ for(int j = i + 1; j <= n; ++j){ if(is_palindrome(0, i, rad) && is_palindrome(i, j, rad)){ ++pp[j]; } } } long long ans = 0; for(int i = 2; i < n; ++i){ for(int j = i + 1; j < n; ++j){ ans += (long long)pp[i] * is_palindrome(j, n, rad); } } cout << ans << endl; } }