### -emli-'s blog

By -emli-, 5 years ago, translation, Hello everyone!

Today 15:00 MSK will be held personal competition.

AtCoder Regular Contest 067

AtCoder Beginner Contest 052

I invite everyone to participate and let's discuss problems after the contest. Comments (9)
•  » » 5 years ago, # ^ | ← Rev. 5 → denotes number of ways of putting people in groups of size . where denotes number of ways to distribute people in groups of size .  .Answer is .
•  » » First observation : a solution will visit a range of restaurants, pick the best meal for each ticket in the range, and pay the distance from the start to the end of the range.It is possible to compute the optimal solution for a range in O(m) time using m range maximum queries and subtracting the distance. This gives a O(n^2 m) algorithm. It is possible to improve it to O(m n log(n)) with divide and conquer optimization.Code for D&D optimization : code// compute optimal values for ranges starting in [l..r-1], ending in [optL..optR] void calc(int l, int r, int optL, int optR){ int mi = (l+r)/2; // find the optimal range starting at mi int optM=optL; int curval=0; FORU(k, max(mi,optL), n-1) { // compute the value of the range [mi..k] int val = computeValue(mi,k); if(val > curval) { curval = val; optM = k; } } // the optimal end for mi is optM ans = max(ans, curval); if(l