https://dmoj.ca/problem/cco07p4

I have been thinking about this problem for a long time now, and I made no progress. The problem seems so easy but it is so difficult. The best I reached was a straightforward $$$O(n^3)$$$ or $$$O(n^2)$$$ dp.

Abridged statement: You are given an $$$n * m$$$ array $$$a$$$ of integers ($$$n$$$ rows, $$$m$$$ columns). In one operation you can merge two rows $$$i$$$, $$$i + 1$$$, and decrement $$$n$$$. When you merge rows, you add their values in each column (So you do $$$a[i][j]$$$ += $$$a[i + 1][j]$$$ for all $$$j$$$, then remove row $$$i + 1$$$). Find the minimum number of merge operations to satisfy the following condition:

The number of rows $$$i$$$ with $$$(a[i][1] > max(a[i][2], ..., a[i][m])$$$ is at least $$$floor(n / 2) + 1$$$.

Constraints:

$$$n <= 10^5$$$

$$$m <= 10$$$