DMOPC '15 Contest 6 P3 - Harvest

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

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

FatalEagle is a diligent farmer who owns a N \times M potato field with exactly one potato on each unit square. Unfortunately, life isn't easy for FatalEagle: while he was away trading on the market, some farmers who were jealous of his bountiful land came and destroyed some of his potatoes. These mysterious foes worked in a methodical manner, destroying some potatoes from every column of the farm. In the i^{th} column (1 \le i \le M), the jealous farmers destroyed all the potatoes from row a_i to row b_i (1 \le a_i \le b_i \le N), inclusive.

When the time came for the annual harvest, FatalEagle found that he was too busy plotting his revenge. However, he still needs to harvest at least K potatoes to feed his family. So he decided that he would buy a tractor of width W, drive it through his field horizontally exactly once, and collect any of the remaining potatoes from W consecutive rows.

FatalEagle doesn't have a lot of money to spend on a tractor, so he would like to know the minimal W so that he can harvest at least K potatoes.


Subtask 1 [20%]

1 \le N, M \le 100

0 \le K \le 10\,000

Subtask 2 [30%]

1 \le N, M \le 3\,000

0 \le K \le 9\,000\,000

Subtask 3 [50%]

1 \le N, M \le 200\,000

0 \le K \le 4 \times 10^{10}

Input Specification

The first line of input will contain three space-separated integers, N, M, and K.

The next M lines will each contain two space-separated integers, a_i and b_i.

Output Specification

Output one integer, the minimal W such that FatalEagle can still harvest at least K potatoes. If it is impossible, output -1.

Sample Input 1

5 5 6
2 5
1 3
4 5
3 3
1 2

Sample Output 1


Explanation for Sample Output 1

The field looks like this, where P represents a potato:


With a tractor of width 2, FatalEagle can harvest the last two rows for exactly 6 potatoes.

Sample Input 2

3 4 7
2 3
1 2
1 3
2 2

Sample Output 2


Explanation for Sample Output 2

Poor FatalEagle only has 4 potatoes left, and therefore cannot feed his family.


  • 15
    NT_AUTHORITY_SYSTEM  commented on June 21, 2017, 12:02 p.m.


    What kind of family consumes 4 * 10 ^ 10 potatoes in a season?

    • 0
      nikos  commented on Sept. 25, 2017, 3:15 p.m.


  • 0
    cheesecake  commented on March 1, 2016, 9:53 p.m.

    Sorry about the confusion with Sample Input 2, the explanation has been corrected.

  • 2
    nullptr  commented on March 1, 2016, 8:24 p.m.

    I don't understand sample input 2. Aren't there only 4 potatoes left?

  • 2
    minecraftyugi  commented on March 1, 2016, 8:24 p.m.

    In sample input 2, how are there 6 potatoes left? If 2 are removed in the first column, 2 in the second, 3 in the third and 1 in the fourth, doesnt that leave 4 potatoes?

  • 1
    nullptr  commented on March 1, 2016, 7:58 p.m.

    What do we do if K=0? Can we have a tractor with zero width?

    • 2
      Zander  commented on March 1, 2016, 8:11 p.m.

      I think you use a tractor of zero width