DMOPC '14 Contest 2 P3 - Sawmill

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M
Author:
FatalEagle
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

Scoring

  • For cases worth 20% of the points, e_i=1 (1 \le e_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, 1 \le i \le N).

Sample Input 1

5
1 1 1 1 1
13 27 6 20 34

Sample Output 1

100

Sample Input 2

3
1 4 2
30 20 10

Sample Output 2

110

Comments


  • 0
    raggarwal  commented on Nov. 19, 2014, 10:21 a.m.

    Can't seem to submit my solution, every time I click submit the Execution Results never updates


    • 0
      raggarwal  commented on Nov. 19, 2014, 10:30 a.m.

      nvm fixed


      • 0
        FatalEagle  commented on Nov. 19, 2014, 10:31 a.m.

        The judge was busy with rejudging submissions.


  • 0
    TuTeMangeras  commented on Nov. 18, 2014, 8:00 p.m.

    IT says i made too many submissions


    • 0
      FatalEagle  commented on Nov. 18, 2014, 9:38 p.m.

      This is because we are rejudging submissions made during the contest.


  • 0
    BMP  commented on Nov. 18, 2014, 7:27 p.m.

    Last one timed out -_-


    • 0
      nikos  commented on Sept. 22, 2017, 7:23 p.m.

      Dont swear ppl


    • 0
      FatalEagle  commented on Nov. 18, 2014, 7:40 p.m.

      Try using Collections.sort


      • 0
        raggarwal  commented on Nov. 19, 2014, 10:30 a.m.

        Im using Collections.sort, however its still timing out for last test case


        • 0
          FatalEagle  commented on Nov. 19, 2014, 10:34 a.m.

          You are still using Arrays.sort for something. Also, keep the answer in a long variable.


          • 0
            raggarwal  commented on Nov. 19, 2014, 12:16 p.m.

            Im not, Im using collections to sort both lists. Will try using a long now.


            • 0
              raggarwal  commented on Nov. 19, 2014, 12:18 p.m.

              Used a long, still nothing :(


              • 0
                FatalEagle  commented on Nov. 19, 2014, 3:35 p.m.

                In submission 12788, you are using Arrays.sort two times. Change both to Collections.sort.


                • 0
                  raggarwal  commented on Nov. 19, 2014, 4:06 p.m.

                  Jeez, I thought I had Collections this whole time. Woops :P

                  Collections runs .5 seconds faster than Arrays.

                  Wowa

                  Good to know.


                  • 0
                    FatalEagle  commented on Nov. 19, 2014, 6:48 p.m.

                    The TLE does not report any time past the time limit. All you know is that your program took at least 1 second to run (it may not terminate at all, but in this case it does). It is possible to construct a test case such that Arrays.sort is O(N^2), and indeed, there is such a case in the test data.


      • 0
        BMP  commented on Nov. 18, 2014, 11:54 p.m.

        Now, I'm getting it wrong :O


        • 1
          FatalEagle  commented on Nov. 19, 2014, 10:35 a.m.

          The final answer will overflow int; use long.


  • -5
    theveggie  commented on Nov. 18, 2014, 5:35 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 0
      FatalEagle  commented on Nov. 18, 2014, 5:47 p.m.

      110 is correct.