Today, I tried F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3). Since $$$n$$$ can be as large as $$$1500$$$, I was struggling to come up with an $$$O(n^2)$$$ but I failed.

When I read the editorial, surprisingly, I found out that the writer's solution is $$$O(n^3)$$$. They used a Hashmap to speedup the whole process, and it seems that the number of different summation values of continuous elements will be less than $$$n^2$$$. Though I cannot find any counterexample such that different sub-array sums can be as large as $$$n^2$$$ (or at least as large as $$$\frac{n \times (n - 1)}{2}$$$), I cannot convince myself an $$$O(n^3)$$$ approach can pass the system test.

I was wondering if you have any analysis to demonstrate that the optimization (using Hashmap) is sufficient, or if you know any bound on the number of different summation of consecutive elements in an arbitrary array.