codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1132C.md (1288B)


      1 Source: https://codeforces.com/problemset/problem/1132/C
      2 
      3 C. Painting the Fence
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have a long fence which consists of $n$ sections. Unfortunately, it is not painted, so you decided to hire $q$ painters to paint it. $i$-th painter will paint all sections $x$ such that $l_i \le x \le r_i$.
     22 
     23 Unfortunately, you are on a tight budget, so you may hire only $q - 2$ painters. Obviously, only painters you hire will do their work.
     24 
     25 You want to maximize the number of painted sections if you choose $q - 2$ painters optimally. A section is considered painted if at least one painter paints it.
     26 
     27 Input
     28 
     29 The first line contains two integers $n$ and $q$ ($3 \le n, q \le 5000$) — the number of sections and the number of painters availible for hire, respectively.
     30 
     31 Then $q$ lines follow, each describing one of the painters: $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).
     32 
     33 Output
     34 
     35 Print one integer — maximum number of painted sections if you hire $q - 2$ painters.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 7 5
     43 1 4
     44 4 5
     45 5 6
     46 6 7
     47 3 5
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 7
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4 3
     60 1 1
     61 2 2
     62 3 4
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 2
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 4 4
     75 1 1
     76 2 2
     77 2 3
     78 3 4
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 3
     85 ```