CodeForces 159D Palindrome pairs

string s が与えられる。
この中に、互いに素な回文、a,bのペアはいくつあるか。

想定解法はDPらしいけど、ごり押しで通った。計算量的にはO(n^2)かO(n^2logn)くらい？

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef long long ll;

int main(){
    string s;
    cin >> s;

    vector<ll> sumto(s.size());
    vector<ll> sumfrom(s.size());
    for(int from=0;from<s.size();from++){
        for(int to=from;to<s.size();to++){
            bool ok = true;
            for(int i=from;i<=to;i++){
                if(s[i] != s[from+to-i]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                sumfrom[from]++;
                sumto[to]++;
            }
        }
    }
    ll ret = 0;
    for(int i=0;i<s.size();i++){
        for(int j=i+1;j<s.size();j++){
            ret += sumto[i] * sumfrom[j];
        }
    }
    cout << ret << endl;
    return 0;
}