ECOO '17 R3 P4 - Ice Cream Beach

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem types

Harnessing your entrepreneurial spirit, you have decided to found a start-up. Your start-up, the first of its kind, will sell ice cream at the local beach. Every day, the beach gets N visitors which sit at specific locations on the beach. The visitors would all love to buy ice cream, but they don't like walking around in the sun. A visitor's reluctance to buy ice cream is calculated by multiplying their distance from the nearest ice cream stand by their reluctance factor: a number unique to each visitor.

You have access to M ice cream stands, which you can place anywhere on the beach. Moreover, you know where every visitor will sit and you know their reluctance factor. Since you don't want your start-up to sink, you'd like to carefully position your stands to minimize the total reluctance of all the visitors.

Can you figure out the minimum total reluctance that you can achieve?

Input Specification

The input contains 10 test cases.

Each test case starts with two integers N (1 \le N \le 4000), M (1 \le M \le 20) where N is the number of visitors and M is the number of ice cream stands. The next N lines describe the visitors coming to the beach. Each line contains two integers X and F, where X represents the locations of the visitor on the beach and F represents the reluctance factor of that visitor (1 \le X, F \le 10^6).

Visitors will be listed in ascending order of X and no two visitors will be at the same location. Since the beach is long and thin, it can be thought of as being one dimensional.

For 30\% of the cases, N \le 10.
For 60\% of the cases, N \le 100.

Output Specification

For each test case, your program should output the minimum total reluctance of all the visitors, modulo 1\,000\,000\,007, or 10^9 + 7. *

Sample Input

2 1
10 10
20 10
2 2
10 10
20 10
4 2
1 10000
100 10
150 10
200 10

Sample Output


Note: Only 3 cases are shown in this sample.

Explanation of Sample Output

In the first test case, it's best to put your only ice cream stand anywhere between positions 10 and 20. If we were to put it at position 15, then each visitor would have a reluctance of 5 \times 10 = 50, for a total reluctance of 100.

In the second test case, you can perfectly accommodate both guests by putting your two carts at locations 10 and 20.

In the last test case, it's best to put one cart at location 1 to appease the incredibly reluctant visitor and put your second cart at location 150.


* This means that if the minimum total reluctance is 999\,999\,999\,999 you should output 999\,993\,006, the remainder after dividing 999\,999\,999\,999 by 1\,000\,000\,007.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at


  • 1
    account_disabled  commented on April 5, 2018, 1:08 p.m. edit 3

    Can anyone give me a hint as to why the last 4 tests per case WA, whereas the first 6 get AC? Just because they are 10x the size doesnt mean they should WA, right?

    EDIT: I forgot to modulo by 10^9 + 7 :/