結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー りあんりあん
提出日時 2020-11-23 07:52:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 445 ms / 2,000 ms
コード長 2,269 bytes
コンパイル時間 2,307 ms
コンパイル使用メモリ 217,128 KB
実行使用メモリ 62,708 KB
最終ジャッジ日時 2023-09-30 23:39:18
合計ジャッジ時間 7,033 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 29 ms
14,340 KB
testcase_06 AC 121 ms
61,924 KB
testcase_07 AC 38 ms
14,912 KB
testcase_08 AC 151 ms
59,556 KB
testcase_09 AC 199 ms
61,192 KB
testcase_10 AC 196 ms
60,608 KB
testcase_11 AC 445 ms
60,360 KB
testcase_12 AC 330 ms
44,544 KB
testcase_13 AC 216 ms
34,168 KB
testcase_14 AC 355 ms
62,544 KB
testcase_15 AC 189 ms
62,336 KB
testcase_16 AC 169 ms
60,224 KB
testcase_17 AC 171 ms
60,608 KB
testcase_18 AC 202 ms
62,600 KB
testcase_19 AC 176 ms
62,604 KB
testcase_20 AC 186 ms
62,708 KB
testcase_21 AC 258 ms
62,700 KB
32_ratsliveonnoevilstar.txt AC 193 ms
62,452 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;
const long long LM = 1LL << 60;


long long solve(const string& s_) {
    string s = "^" + s_;
    int n = s.length();
    vector<vector<long long>> pl(n, vector<long long>(3, 0)), gpl(n, vector<long long>(3, 0));
    pl[0][0] = 1;
    vector<tuple<int, int, int>> g;
    for (int j = 1; j < n; ++j) {
        vector<tuple<int, int, int>> g1, g2;
        for (auto [i, d, k] : g) {
            if (i > 0 && s[i - 1] == s[j]) {
                g1.emplace_back(i - 1, d, k);
            }
        }
        int r = -j;
        for (auto [i, d, k] : g1) {
            if (i - r != d) {
                g2.emplace_back(i, i - r, 1);
                if (k > 1) {
                    g2.emplace_back(i + d, d, k - 1);
                }
            }
            else {
                g2.emplace_back(i, d, k);
            }
            r = i + (k - 1) * d;
        }
        if (j > 1 && s[j - 1] == s[j]) {
            g2.emplace_back(j - 1, j - 1 - r, 1);
            r = j - 1;
        }
        g2.emplace_back(j, j - r, 1);
        g.clear();
        for (auto [i, d, k] : g2) {
            if (g.empty() || get<1>(g[(int)g.size() - 1]) != d) {
                g.emplace_back(i, d, k);
            }
            else {
                get<2>(g[(int)g.size() - 1]) += k;
            }
        }
        for (auto [i, d, k] : g) {
            r = i + (k - 1) * d;
            vector<long long> m = { 0LL, pl[r - 1][0], pl[r - 1][1] };
            if (k > 1) {
                m[1] += gpl[i - d][1];
                m[2] += gpl[i - d][2];
            }
            if (d <= i) {
                gpl[i - d] = m;
            }
            pl[j][1] += m[1];
            pl[j][2] += m[2];
        }
    }

    long long ans = 0;
    vector<long long> a(n);
    a[0] = pl[0][2];
    for (int i = 1; i < n; ++i) {
        a[i] = a[i - 1] + pl[i][2];
    }
    for (auto [i, d, k] : g) {
        for (int j = 0; j < k; ++j) {
            if (i + d * j > 1) {
                ans += a[i + d * j - 2];
            }
        }
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    cout << solve(s) << '\n';
    return 0;
}
0