結果

問題 No.464 PPAP
ユーザー hiro71687k
提出日時 2023-08-23 07:27:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 282 ms / 2,000 ms
コード長 2,115 bytes
コンパイル時間 3,643 ms
コンパイル使用メモリ 253,716 KB
最終ジャッジ日時 2025-02-16 12:25:58
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll mod=1000000007;
ll inf=1009999999999999990;
int main(){
    string s;
    cin >> s;
    string ss;
    for (ll i = 0; i < s.size(); i++)
    {
        ss.push_back(s[i]);
        ss.push_back('@');
    }
    s=ss;
    ll n=s.size();
    vector<bool>dp1(n,0);
    vector<bool>dp3(n,false);
    for (ll i = n-2; i >=0; i--)
    {
        string t;
        for (ll j = n-2; j >=i; j--)
        {
            t.push_back(s[j]);
        }
        ll tt=t.size();
        bool o=true;
        for (ll j = 0; j < tt; j++)
        {
            if (t[j]!=t[tt-1-j])
            {
                o=false;
                break;
            }
        }
        dp3[i]=o;
    }
    for (ll i = 0; i < n; i++)
    {
        string t;
        for (ll j = 0; j <= i; j++)
        {
            t.push_back(s[j]);
        }
        ll tt=t.size();
        bool o=true;
        for (ll j = 0; j < tt; j++)
        {
            if (t[j]!=t[tt-1-j])
            {
                o=false;
                break;
            }
        }
        dp1[i]=o;
    }
    ll x=0,y=0;
    vector<ll>r(s.size(),0);
    while (x<s.size())
    {
        while (x-y>=0&&x+y<s.size()&&s[x-y]==s[x+y])
        {
            y++;
        }
        r[x]=y;
        ll k=1;
        while (x-k>=0&&k+r[x-k]<y)
        {
            r[x+k]=r[x-k];
            k++;
        }
        x+=k;
        y-=k;
    }
    vector<ll>memo(n,0);
    for (ll i = n-2; i >=0; i--)
    {
        memo[i]=memo[i+1];
        if (dp3[i+1])
        {
            memo[i]++;
        }
    }
    ll ans=0;
    for (ll i = 1; i < n; i++)
    {
        for (ll j = 0; j <r[i]; j++)
        {
            if (s[i]=='@'&&j==0)
            {
                continue;
            }
            
            if (i-j<=0||i+j>=n-1)
            {
                break;
            }
            if (dp1[i-j-1])
            {
                ans+=memo[i+j+1];
            }
        }
    }
    cout << ans << endl;
}
0