Cod sursa(job #637850)

Utilizator SmarandaMaria Pandele Smaranda Data 20 noiembrie 2011 17:09:32
Problema PalM Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.66 kb
#include<cstdio>
#include<vector>
#include<string>
using namespace std;
int main() {
	long i,n,j,l,st,dr,l1,v,w,max=-1,ind;
	char s[501];
	char aux;
	string f;
	
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	
	gets(s);
	string x(s);
	n=x.length();
	for (i=0;i<n;i++) {
		string s1(x,0,i);
		l1=s1.length();
		string s2(x,i+1,n-1-(i+1)+1);
		l=s2.length();
		st=0;
		dr=l-1;
		while (st<=dr) {
			aux=s2[st];
			s2[st]=s2[dr];
			s2[dr]=aux;
			st++;
			dr--;
		}
		long c[522][522];
		for (v=0;v<=l1;v++)
			c[v][0]=c[v][l+1]=0;
		for (w=0;w<=l;w++)
			c[0][w]=c[l1+1][w]=0;
		for (v=1;v<=l1;v++)
			for (w=1;w<=l;w++)
				if (s1[v-1]==s2[w-1])
					c[v][w]=c[v-1][w-1]+1;
				else 
					if (c[v][w-1]>c[v-1][w])
						c[v][w]=c[v][w-1];
					else
						c[v][w]=c[v-1][w];
		f.clear();
		v=l1-1;
		w=l-1;
		while (v && w) {
			if (s1[v]==s2[w]) {
				f.push_back(s1[v]);
				v--;
				w--;
			}
			else
				w--;
		}
		l=f.length();
		st=0;
		dr=l-1;
		while (st<=dr) {
			aux=f[st];
			f[st]=f[dr];
			f[dr]=aux;
			st++;
			dr--;
		}
		long ok=1;
		for (j=1;j<l && ok;j++) 
			if (f[j]<f[j-1])
				ok=0;
		aux=f[l-1];
		ind=l-1;
		if (ok==0) {
			long L=1,lmax=1;
			aux=f[0];
			ind=0;
			for (j=1;j<l;j++)
				if (f[j]>f[j-1])
					L++;
				else {
					if (L>lmax) {
						lmax=L;
						aux=f[j-1];
						ind=j-1;
					}
					L=1;
				}
			ok=1;
			l=lmax;
		}
		if (ok==1)
			if (aux>x[i]) {
				for (j=ind;j>=ind-l+1;j--)
					if (f[j]<x[i])
						break;
					else 
						l--;
				ok=1;
			}
		if (ok==1)
			if (2*l+1>max)
				max=2*l+1;
	}
	printf("%ld\n",max);
	return 0;
}