There are some AC solutions which are actually O(N^3).
Here is the test when some of them fail (3.42s):
#include <iostream>
#include <fstream>
using namespace std;

int main() {
    ofstream fout("test.txt");

    for (int i = 0; i < 1000; i++)
        fout << (char)(i%26+'a');

    return 0;
}

What is the example of such AC solution (submit ID or source code)?