DMOPC '14 Contest 2 P3 - Sawmill

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

The Logging Company owns many sawmills. However, these sawmills currently require a human operator to function. To decrease wage expenses, the Company has hired you to write a program to replace all the humans at the sawmills.

At the sawmill, there are N saws and N logs (1 \le N \le 50\,000). The task of an operator is to coordinate which saws should saw which logs. Each saw has an energy consumption rate e_i, and each log has a length l_i. Each saw should only saw one log per day, to prevent overheating. The total energy a saw needs to saw a log is its energy consumption rate multiplied by the log's length. To prove that your program can do the operators' jobs better than they can, you want to assign logs to saws such that the total energy used per day is minimized.

Input Specification

  • The first line will be N, the number of saws and logs.
  • The second line will contain N integers, the energy consumption of each saw, e_i (1 \le e_i \le 50\,000, 1 \le i \le N).
  • The third line will contain N integers, the length of each log, l_i (1 \le l_i \le 50\,000, 1 \le i \le N).

Output Specification

The first and only line of output should be the minimum total energy used on the day described by the input.


  • For cases worth 20% of the points, e_i=1 for all 1 \le i \le N.
  • For cases worth another 30% of the points, N \le 100.
  • For cases worth another 20% of the points, N \le 5\,000.
  • For cases worth 90% of the points in total, 1 \le e_i, l_i \le 200 for all 1 \le i \le N.

Sample Input 1

1 1 1 1 1
13 27 6 20 34

Sample Output 1


Sample Input 2

1 4 2
30 20 10

Sample Output 2



There are no comments at the moment.