結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー りあんりあん
提出日時 2020-11-23 07:51:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,257 bytes
コンパイル時間 2,280 ms
コンパイル使用メモリ 216,892 KB
実行使用メモリ 60,632 KB
最終ジャッジ日時 2023-09-30 23:38:49
合計ジャッジ時間 6,970 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 27 ms
14,112 KB
testcase_06 AC 118 ms
59,908 KB
testcase_07 AC 36 ms
14,316 KB
testcase_08 AC 149 ms
57,844 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 441 ms
58,588 KB
testcase_12 AC 325 ms
43,312 KB
testcase_13 AC 212 ms
33,360 KB
testcase_14 AC 349 ms
60,616 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 183 ms
60,384 KB
testcase_21 AC 252 ms
60,624 KB
32_ratsliveonnoevilstar.txt WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


int 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<int> 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