Submission #40073

#	Time	Username	Problem	Language	Result	Execution time	Memory
40073		5ak0	Palinilap (COI16_palinilap)	C++14	17 / 100	1000 ms	2372 KiB

palinilap

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 5010;

string s;
int ans;
int d[MAXN], d2[MAXN];

int calc(string c){
    int n = c.size();
    int l, r;
    l = r = -1;
    for (int i = 0; i < n; i++)
    {
        d[i] = 1;
        if (i <= r)
            d[i] = min(r - i + 1, d[l + (r - i)]);
        while (i + d[i] < n && i - d[i] >= 0 && c[i - d[i]] == c[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    l = r = -1;
    for (int i = 0; i < n; i++)
    {
        d2[i] = 0;
        if (i <= r)
            d2[i] = min(r - i, d2[l + (r - i) - 1]);
        while (i + d2[i] + 1 < n && i - d2[i] >= 0 && c[i - d2[i]] == c[i + d2[i] + 1])
        {
            d2[i]++;
        }
        if (i + d2[i] > r)
            l = i - d2[i] + 1, r = i + d2[i];
    }
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += (d[i] - 1);
        ans += d2[i];
    }
    return ans + c.size();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin >> s;
    ans = calc(s);
    for (int i = 0; i < s.size(); ++i){
        char ch = s[i];
        for (char j = 'a'; j <= 'z'; ++j){
            s[i] = j;
            ans = max(ans, calc(s));
        }
        s[i] = ch;
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i){
                       ^

• Subtask 1: 17 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46