Convex / Concave Optimization DP

IOICJ 91 Printer ( DP, 1D / 1D Convex Optimization )

Problem Description: You have a book with N pages in total. Page i requires cost A[ i ] to be printed. You have a weird printer, the cost of printing a continuous segment [ L, R ) is ( Sigma{ A[ i ], L ≤ i Constraints: 1≤T≤100 1≤N≤1e5 1≤K≤…