結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー りあんりあん
提出日時 2020-11-23 07:52:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 438 ms / 2,000 ms
コード長 2,269 bytes
コンパイル時間 2,508 ms
コンパイル使用メモリ 220,280 KB
実行使用メモリ 62,824 KB
最終ジャッジ日時 2024-07-23 17:20:31
合計ジャッジ時間 7,045 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 28 ms
14,568 KB
testcase_06 AC 121 ms
62,096 KB
testcase_07 AC 35 ms
15,104 KB
testcase_08 AC 145 ms
59,988 KB
testcase_09 AC 194 ms
61,228 KB
testcase_10 AC 201 ms
60,956 KB
testcase_11 AC 438 ms
60,524 KB
testcase_12 AC 323 ms
44,852 KB
testcase_13 AC 213 ms
34,404 KB
testcase_14 AC 353 ms
62,700 KB
testcase_15 AC 185 ms
62,316 KB
testcase_16 AC 163 ms
60,264 KB
testcase_17 AC 164 ms
60,776 KB
testcase_18 AC 194 ms
62,676 KB
testcase_19 AC 168 ms
62,696 KB
testcase_20 AC 182 ms
62,692 KB
testcase_21 AC 253 ms
62,824 KB
32_ratsliveonnoevilstar.txt AC 183 ms
62,784 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