Cod sursa(job #635495)

Utilizator SpiderManSimoiu Robert SpiderMan Data 19 noiembrie 2011 12:14:36
Problema PalM Scor 10
Compilator cpp Status done
Runda .com 2011 Marime 1.67 kb
#include <fstream>
#include <cstring>
using namespace std;

int n, sol = 1, lvec;
int vec[510];
char a[510];
bool mat[510][510];
bool mmx[510][510], mmn[510][510];

int main()
{
    ifstream f("palm.in");
    ofstream g("palm.out");

    f >> a;
    n = strlen(a);

    for (int i = 1; i <= n; ++i) // pentru 1 si 2 : )
        mat[i][i] = true, mat[i][i + 1] = (a[i] == a[i + 1] ? true : false);

    for (int i = 3; i <= n; ++i) // lungimea
        for (int j = 1; j <= n; ++j) // pozitia de start
        {
            if (mat[j + 1][j + i - 2] == true && a[j] == a[j + i - 1])
                mat[j][j + i - 1] = true;
        }

    for (int i = 1; i <= n; ++i)
    {
        char mx = 0, mn = 250;
        bool ok1 = 1, ok2 = 1;
        for (int j = i; j <= n; ++j)
        {
            if (mx <= a[j] && ok1) mmx[i][j] = true;
            else ok1 = false;
            if (mn >= a[j] && ok2) mmn[i][j] = true;
            else ok2 = false;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            if (mat[i][j])
            {
                if ((j - i + 1) % 2 == 0) // par
                {
                    int mid = (i + j) >> 1;
                    if (mmx[i][mid] && mmx[mid][j])
                        sol = (sol < j - i + 1 ? j - i + 1 : sol);
                }
                else
                {
                    int mid = (i + j) >> 1;
                    if (mmx[i][mid] && mmx[mid][j])
                        sol = (sol < j - i + 1 ? j - i + 1 : sol);
                }
            }
        }
    }

    g << sol << '\n';
    g.close();
    return 0;
}