Submission #46322

#	Time	Username	Problem	Language	Result	Execution time	Memory
46322		RayaBurong25_1	Palindromes (APIO14_palindrome)	C++17	47 / 100	1090 ms	16072 KiB

palindrome

#include <stdio.h>
#include <map>
#define MOD 1000000007LL
char S[300005];
std::map<int, int> Map[300005];
int isPalin[2][300005];
int Ans = 0;
int main()
{
    scanf("%s", S);
    int N;
    for (N = 0; S[N] != '\0'; N++);
    int i, j;
    long long Hash;
    std::map<int, int>::iterator it;
    for (i = N - 1; i >= 0; i--)
    {
        Hash = 0;
        for (j = i; j < N; j++)
        {
            Hash = (Hash*26 + S[j] - 'a')%MOD;
            if (j == i)
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else if (j == i + 1 && S[i] == S[j])
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else if (S[i] == S[j] && isPalin[(i + 1)%2][j - 1])
            {
                isPalin[i%2][j] = 1;
                Map[j - i + 1][Hash]++;
                it = Map[j - i + 1].find(Hash);
                if (it->second*(j - i + 1) > Ans)
                    Ans = it->second*(j - i + 1);
            }
            else
                isPalin[i%2][j] = 0;
            // printf("i%d j%d isPalin %d\n", i, j, isPalin[i%2][j]);
        }
    }
    printf("%d", Ans);
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S);
     ~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27