Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_14_20 - Dachy |
Jaś zabrał się za uprawę bananów. Nie wziął jednak pod uwagę, że klimat potrafi być bardzo surowy, więc teraz musi przygotować odpowiednie zadaszenie.
Jaś ma długą farmę o wymiarach 2xN. Na niektórych polach rosną palmy. Celem jest pokrycie wszystkich D palm prostokątnymi dachami. Dachy mogą być dowolnymi prostokątami o całkowitych wymiarach. Nie mogą wychodzić poza obszar farmy ale mogą pokrywać puste pole. Dachy nie mogą się pokrywać.
Twoje zadanie to policzyć jaka jest najmniejsza możliwa powierzchnia K dachów, które pokryją wszystkie palmy.
Wejście
W pierwszej linii wejścia znajduje się t - liczba zestawów danych (t ≤ 10).
Każdy test wygląda następująco:
Na początku podane są trzy liczby: D - liczba palm (D ≤ 2500), K - liczba dachów (K ≤ D), N - rozmiar pola (N ≤ 106).
W kolejnych D liniach znajdują się pary liczb a, b oznaczające współrzędne kolejnych palm (a ∈ [1,2], b ∈ [1, N]).
Wyjście
Najmniejsza powierzchnia K dachów, które przykryją wszystkie D palmy.
Przykład
Wejście:
2
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
6 2 100
1 1
1 2
1 3
2 2
2 3
2 4
Wyjście:
10
6
Dodane przez: | Grzegorz Spryszyński |
Data dodania: | 2021-12-17 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |