結果

問題 No.464 PPAP
ユーザー hiro71687khiro71687k
提出日時 2023-08-23 07:27:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 2,115 bytes
コンパイル時間 5,087 ms
コンパイル使用メモリ 262,104 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-23 07:27:49
合計ジャッジ時間 7,896 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 14 ms
4,376 KB
testcase_08 AC 12 ms
4,376 KB
testcase_09 AC 11 ms
4,376 KB
testcase_10 AC 300 ms
4,376 KB
testcase_11 AC 149 ms
4,380 KB
testcase_12 AC 236 ms
4,376 KB
testcase_13 AC 215 ms
4,380 KB
testcase_14 AC 258 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 216 ms
4,380 KB
testcase_24 AC 214 ms
4,376 KB
testcase_25 AC 215 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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