Cod sursa(job #2795413)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 6 noiembrie 2021 12:21:15
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <stdio.h>
#include <ctype.h>

using namespace std;
const int NMAX = 1000000;

int dpRmax[NMAX * 2 + 3];
char s[NMAX*2 + 3];
inline int mymin(int a, int b);

int main()
{
    int n, ccur, rcur, cnou, rnou;
    long long sum = 0;
    char ch;
    s[0] = '&';
    s[1] = '*';
    n = 2;
    FILE *fin = fopen("pscpld.in", "r");
    while (isalpha(ch = fgetc(fin)))
    {
        s[n++] = ch;
        s[n++] = '*';
    }

    fclose(fin);

    ccur = rcur = 0;
    for (cnou = 2; cnou < n; cnou++)
    {
        if (ccur + rcur <= cnou)
            rnou = 0;
        else
            rnou = mymin(dpRmax[cnou], (ccur << 1) - cnou);
        while (s[cnou + rnou + 1] == s[cnou - rnou - 1])
            rnou++;
        dpRmax[cnou] = rnou;
        sum += (long long)((rnou + 1) >> 1);

        if (cnou + rnou > ccur + rcur)
        {
            ccur = cnou;
            rcur = rnou;
        }

    }
    FILE *fout = fopen("pscpld.out", "w");
    fprintf(fout, "%lld", sum);
    fclose(fout);
    return 0;
}

inline int mymin(int a, int b)
{
    if (a < b)
        return a;
    return b;
}