#include <stdio.h> #include <string.h> #include <assert.h> #define sqr(x) ((x) * (x)) #define max(x, y) ((x) > (y) ? (x):(y)) #define min(x, y) ((x) < (y) ? (x):(y)) int delta[200][200][3]; int xxx[200][200]; int yyy[200][200]; char chr[200]; int len[200]; int n; int main() { int l, i, i1, j, k; char cmd[201]; int ncmd; while(scanf("%s", cmd) != EOF) { ncmd = strlen(cmd); n = 0; for(i = 0; i < ncmd; ++i) { if(cmd[i] == 0 || cmd[i] != cmd[i - 1]) { i1 = i; } if(i == ncmd - 1 || cmd[i] != cmd[i + 1]) { chr[n] = cmd[i]; len[n] = i - i1 + 1; ++n; } } assert(n >= 1); for(i = 0; i < n; ++i) { delta[i][i][0] = sqr(max(len[i], 2) + 1); delta[i][i][1] = sqr(max(len[i], 2) + 1); delta[i][i][2] = -1; xxx[i][i] = sqr(max(len[i], 2) + 1); yyy[i][i] = -1; } for(l = 2; l <= n; ++l) for(i = 0; i + l <= n; ++i){ j = i + l - 1; xxx[i][j] = -1; if(chr[i] == chr[j]) { if(len[i] >= 2) { if(xxx[i][j] == -1 || sqr(len[i] + max(len[j], 2)) + yyy[i + 1][j] > xxx[i][j]) xxx[i][j] = sqr(len[i] + max(len[j], 2)) + yyy[i + 1][j]; } else { for(i1 = i; i1 < j; ++i1) { if(chr[i1] != chr[i])continue; if(len[i1] != 1)continue; if(i1 == i) {if(xxx[i][j] == -1 || sqr(2 + max(len[j], 2)) + yyy[i1 + 1][j] > xxx[i][j]) { xxx[i][j] = sqr(2 + max(len[j], 2)) + yyy[i1 + 1][j];} } else {assert(delta[i + 1][i1 - 1][1] != -1);if(xxx[i][j] == -1 || sqr(2 + max(len[j], 2)) + delta[i + 1][i1 - 1][1] + yyy[i1 + 1][j] > xxx[i][j]) { xxx[i][j] = sqr(2 + max(len[j], 2)) + delta[i + 1][i1 - 1][1] + yyy[i1 + 1][j];} } } } assert(xxx[i][j] != -1); } yyy[i][j] = -1; if(i != 0 && chr[i - 1] == chr[j]) { if(len[j] >= 2) { assert(delta[i][j - 1][1] != -1); if(yyy[i][j] == -1 || delta[i][j - 1][1] > yyy[i][j]) yyy[i][j] = delta[i][j - 1][1]; } else { for(i1 = j; i1 > i; --i1) { if(chr[i1] != chr[j])continue; if(len[i1] != 1)continue; if(i1 == j) {assert(delta[i][i1 - 1][1] != -1);if(yyy[i][j] == -1 || delta[i][i1 - 1][1] > yyy[i][j]) yyy[i][j] = delta[i][i1 - 1][1]; } else {assert(delta[i][i1 - 1][1] != -1);assert(delta[i1 + 1][j - 1][1] != -1);if(yyy[i][j] == -1 || delta[i][i1 - 1][1] + delta[i1 + 1][j - 1][1] > yyy[i][j]) yyy[i][j] = delta[i][i1 - 1][1] + delta[i1 + 1][j - 1][1]; } } } assert(yyy[i][j] != -1); } delta[i][j][0] = delta[i][j][1] = delta[i][j][2] = -1; for(i1 = i; i1 <= j; ++i1) { if(chr[i1] != chr[i]) continue; if(i1 == j) { for(k = 0; k <= 1; ++k) { if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][j])delta[i][j][k] = xxx[i][j]; } continue; } if(delta[i][j][0] == -1 || delta[i][j][0] < xxx[i][i1] + delta[i1 + 1][j][0]) delta[i][j][0] = xxx[i][i1] + delta[i1 + 1][j][0]; for(k = 1; k <= 2; ++k) { if(i == 0 || chr[i - 1] != chr[i1 + 1]) { if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][i1] + delta[i1 + 1][j][0])delta[i][j][k] = xxx[i][i1] + delta[i1 + 1][j][0]; } else { if(delta[i1 + 1][j][2] != -1) if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][i1] + delta[i1 + 1][j][2])delta[i][j][k] = xxx[i][i1] + delta[i1 + 1][j][2]; } } } assert(delta[i][j][0] != -1); } printf("%dn", delta[0][n - 1][0]); } return 0; }
