How can i improve my O(n ^ 2 * logN) time and O(n * n) memory too pass all tests?
int n, y[2004], index = 1, maximum = 1, rati;
pair<int, int> x[2004];
map<int, int> s[2004];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i].first;
        x[i].second = i;
        y[i] = 1;
    }
    sort(x, x + n);
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++){
            if(y[i] < s[j][x[i].first - x[j].first] + 2 && x[i].first - x[j].first != 0){
                y[i] = s[j][x[i].first - x[j].first] + 2;
                if(maximum < y[i]){
                    index = i;
                    maximum = y[i];
                    rati = x[i].first - x[j].first;
                }
            }
            s[i][x[i].first - x[j].first] = s[j][x[i].first - x[j].first] + 1;
        }
    }
    cout << maximum << "\n";
    int val = x[index].first, i;
    cout << x[index].second + 1 << " ";
    for(i = index - 1; i >= 0; i--)
    {
        if(val - x[i].first == rati && rati != 0)
        {
            val = x[i].first;
            cout << x[i].second + 1 << " ";
        }
    }
    return 0;
}

You can use a hashmap instead of a red-black tree to get AC. Just remember to use the __gnu_pbds::cc_hash_table (header <ext/pb_ds/assoc_container.hpp>) as it's about 3 times faster than the std::unordered_map.