Submission #1351651

#TimeUsernameProblemLanguageResultExecution timeMemory
1351651AliyyiakbarPalinilap (COI16_palinilap)C++20
17 / 100
1096 ms1348 KiB
#include <bits/stdc++.h>
/// #include "AkbarKING.h"
#define int long long
#define endl '\n'
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;

const int sz = 2e5 + 9;
const int MOD = 1e9 + 7;
const int INF = 1e18;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();
    int total = 0;
    vector<int> cnt(n + 5);
    for (int fix = 0; fix < n; ++fix)
    {
        int l = fix, r = fix;
        while(l >= 0 && r < n && s[l] == s[r])
        {
            ++total;
            ++cnt[l];
            --cnt[r + 1];
            --l;
            ++r;
        }
        l = fix, r = fix + 1;
        while(l >= 0 && r < n && s[l] == s[r])
        {
            ++total;
            ++cnt[l];
            --cnt[r + 1];
            --l;
            ++r;
        }
    }
    for (int i = 1; i < n; ++i)
    {
        cnt[i] += cnt[i - 1];
    }
    int res = total;
    for (int pos = 0; pos < n; ++pos)
    {
        char tmp = s[pos];
        for (char ch = 'a'; ch <= 'z'; ++ch)
        {
            s[pos] = ch;
            int now = 0;
            for (int i = 0; i < n; ++i)
            {
                for (int delta = 0; delta <= min(i, n - i - 1); ++delta)
                {
                    if (s[i - delta] != s[i + delta])
                    {
                        break;
                    }
                    if (i - delta <= pos && pos <= i + delta)
                    {
                        ++now;
                    }
                }
            }
            for (int i = 0; i + 1 < n; ++i)
            {
                for (int delta = 0; delta <= min(i, n - i - 2); ++delta)
                {
                    if (s[i - delta] != s[i + delta + 1])
                    {
                        break;
                    }
                    if (i - delta <= pos && pos <= i + delta + 1)
                    {
                        ++now;
                    }
                }
            }
            res = max(res, total - cnt[pos] + now);
        }
        s[pos] = tmp;
    }
    cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...