Today, I tried [F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3)](https://mirror.codeforces.com/problemset/problem/1141/F2). 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 continuoussecutive 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.
↵
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 con
↵
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.
