Let the DP state be:

1. $$$i$$$, the length of the actual string.
2. $$$l$$$, the length of the run-length encoded string.
3. $$$c$$$, the last character in the string.

Think of a transition where you add $$$c'$$$ $$$k$$$ times. In the run-length encoded string, that is equivalent to adding $$$f(k)+1$$$ characters, where $$$f(k)$$$ is the length of $$$k$$$ when written as a number. Since $$$n < 3000$$$, $$$f(k) \leq 4$$$. So, you can transition from $$$dp_{i,l,c}$$$ to $$$dp_{i+k,l+f(k)+1, c'}$$$, for 4 different ranges of $$$k$$$.

Note that the DP transitions will actually be symmetric w.r.t $$$c$$$, i.e. $$$dp_{i,l,c} = dp_{i,l,c'}$$$ for all $$$i,l$$$. With this knowledge, we can just knock that dimension out, making the transition adding $$$25 \cdot dp_{i,l}$$$ to $$$dp_{i+k, l+f(k)+1}$$$. You don't need any complicated structures to add to the ranges of $$$k$$$, you can do this by adding in a prefix-sum-esque way and adding to $$$l$$$ and subtracting from $$$r+1$$$. Hence, you can do the entire DP in $$$O(n^2)$$$.

I requested that clarification. It's lucky that as a Chinese I can comprehend at least some Japanese.

At least "meters a second" should be "meters per second".

Just keep the no. of times a number has appeared in the array. Factor (not prime factor) the number and use some simple combinatorics. It should be done in $$$O(n\sqrt n)$$$.

for (auto x : d) {
    ll res = 0;
    for (int j = 1; j * j <= x; j++) {
      if (x % j == 0) {
        if (j != x / j)
          res += cnt[j] * cnt[x / j] * 2;
        else
          res += cnt[j] * (cnt[j] - 1) + cnt[j];
        //    cerr << j << ": " << res << ", ";
      }
    }
    res *= cnt[x];
    //   cerr << res << endl;
    ans += res;
  }

Actually in D, I am not able to see how ans for sample 3 equals 62?

Just guessing: I think the access-patterns on mp.count(v[i] / j) are more cache-friendly in the sorted case, at least for low values of i. In the unsorted case you have less loop iterations where both v[i] and v[i+1] are low.

The editorial is out now.

My solution to problem F: Let we add an operation $$$t_0=1,y_0=0$$$. Then, the final value of $$$x$$$ is always consisted of $$$y_i(t_i=1)$$$ and the sum of some(not all) $$$y_j(t_j=2,i<j\le n)$$$. (We will ignore the operations with $$$t_j=1$$$)

In the operations with $$$t_j=2$$$, we can always ignore the smallest negative $$$y_j$$$ to reach the maximum value of $$$x$$$. Thus, the problem becomes maintaining $$$val=\text{the sum of the smallest negative }k'\text{-th } y_j$$$ ($$$k'=k- \text{the number of operations with } t_j=1(i<j\le n)$$$), and this can be done by balance tree, priority queue, segment tree, etc.

My implementation: deal with the operations from $$$n$$$ to $$$0$$$. If $$$t_i=2$$$ and $$$y_i<0$$$, insert it to the treap, then do $$$s\leftarrow s+y_i$$$. If $$$t_i=1$$$, do $$$ans\leftarrow\max(ans,y_i+s-val),k'\leftarrow k'-1$$$.($$$val$$$ is mentioned above)

my code using treap