We can actually prove it by proving that we can never merge islands of 3's. (2's are fixed). I got 1e9+7 WAs before noticing that we have to run the loop backwards as well for smth like 233312 😭

damn I almost thought something like this going forward then backward but didnt try

When I came up with the problem, I had a more complicated casework-y solution, and only later realized that the simple greedy implementation is actually correct.

I was not sure how guessable this was so I briefly considered modifying the problem to ask for the answer for every prefix or something like that, but after discussing with the tester we decided it's fine to keep it as-is, since for the most part I feel like if you're able to think of this algorithm then it's not too hard to prove it either. (Also it makes for a simple implementation which is always nice.)

I did make sure to modify the samples so that just iterating forward would pass them though :) (you're welcome RoomTemperatureIQ)

I assume you're doing "memset" for each case?

You are reinitializing it to dp[4][300005] in each testcase , which prolly gives the TLE, even if you don't get TLE , you will get WA, since this would not consider the cases that the backward iteration considers in the AC solution.

Congrats hxu10 on being red !

same, i thought that my greedy solution was missing something and did not end up implementing it