tag:blogger.com,1999:blog-29632375.post1189618196008667332..comments2015-07-26T10:48:18.008-07:00Comments on vexorian's blog: Codeforces round #107 : "undefined"Unknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-29632375.post-1500170941595225952012-02-17T17:07:27.641-08:002012-02-17T17:07:27.641-08:00You can turn the sum of consecutives into a differ...You can turn the sum of consecutives into a difference of two accumulated sums.Mario Ynocente Castrohttp://www.facebook.com/MarioYCnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-74075710470442233542012-02-17T10:45:26.343-08:002012-02-17T10:45:26.343-08:00It seems this is the favorite approach in general....It seems this is the favorite approach in general. Perhaps there is something about implementation to optimize finding the best consecutive sum. But O(m * sqrt(n)) seems fine or just an extra step behind working bellow the limit.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-357883634831400742012-02-17T10:22:29.150-08:002012-02-17T10:22:29.150-08:00Wow, you've put up a blog in no time! For Div1...Wow, you've put up a blog in no time! For Div1C / Div2E, I thought of an O( m * sqrt(n) + n ) solution along these lines. For each passenger, a segment must be chosen that has the maximum expected profit. For each of the n-1 legs, expected profit can be calculated( if ticket is not taken) and stored in an array. Split this array into sqrt(n) blocks, each of same size( except for the last one) and after a few pre-calculations on these blocks, the maximum expected profit can be calculated for each passenger in O(sqrt(n)) time (Involves calculating the maximum consecutive sum ). Not sure, if this will run under the time limit, though.<br /><br />Vinay Emani.Vinay Emanihttp://www.facebook.com/vinayemaninoreply@blogger.com