Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S_{1}, S_{2}, S_{3}, S_{4} ... S_{x}, ... S_{n} (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S_{x} ≤ 32767). We define a function sum(i, j) = S_{i} + ... + S_{j} (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i_{1}, j_{1}) + sum(i_{2}, j_{2}) + sum(i_{3}, j_{3}) + ... + sum(i_{m}, j_{m}) maximal (i_{x} ≤ i_{y} ≤ j_{x} or i_{x} ≤ j_{y} ≤ j_{x} is not allowed).

But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i_{x}, j_{x})(1 ≤ x ≤ m) instead. ^_^

Given a consecutive number sequence S

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i

But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i

提交代码