| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
POTKON1 - Konferencja |
W Bitogrodzie trwają przygotowania do dorocznej Wielkiej Konferencji Bitonicznej. W ramach konferencji odbędzie się m prezentacji, które - zgodnie z tradycją - muszą odbywać się dokładnie w tym samym czasie. Wszystkie prezentacje przeprowadzane są w identycznych salach. Każda sala jest w stanie pomieścić co najwyżej k uczestników. Liczba sal jest wystarczająca do pomieszczenia wszystkich prezentacji. Jeśli w prezentacji uczestniczy więcej niż k słuchaczy, to organizatorzy muszą zarezerwować większą liczbę sal. Organizatorzy konferencji chcą zmaksymalizować swoje zyski - suma uzyskana ze sprzedaży biletów, pomniejszona o koszt wynajęcia sal, powinna być jak największa. Koszt wynajmu każdej z sal jest równy s. Bilet wstępu dla jednej osoby na i-tą prezentację kosztuje ci. Ceny biletów zostały tak dobrane, aby na pewno opłacalne było wynajęcie sali dla [k/2] ( gdzie, [x] - podłoga z liczby x, to największa liczby naturalna m taka, że m<=x) osób (ale być może opłaca się również dla mniejszej liczby osób), czyli zysk z wynajęcia jest w takim przypadku nieujemny. Organizatorzy chcą unieważnić niektóre zarezerwowane bilety w celu zmaksymalizowania zysków. Ponieważ Ty pisałeś system rejestracji na konferencję, zatem Tobie przypadło w udziale wykonanie tego zadania.
Zadanie
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite: m, l, k, s (1<=m<=100, 2<=l<=1 000 000, 2<=k<=400, 1<=s<=1000), pooddzielane pojedynczymi odstępami. Liczby te reprezentują odpowiednio: liczbę przeprowadzonych prezentacji, liczbę dokonanych rezerwacji, wielkość każdej z sal oraz koszt wynajęcia jednej sali. Drugi wiersz zawiera dokładnie m liczb 0<=ci <=s, pooddzielanych pojedynczymi odstępami. Są to ceny biletów na kolejne prezentacje. Kolejne l wierszy zawiera opisy dokonanych rezerwacji. Każda rezerwacja jest przez określona przez dwie liczby całkowite p oraz r (1<=p<=m, 1<=r<=1000), oddzielone pojedynczym odstępem. Reprezentują one odpowiednio numer prezentacji, na którą dokonywana jest rezerwacja oraz liczbę rezerwowanych biletów. Dozwolone jest wycofanie dowolnej liczby zarezerwowanych biletów, a nie tylko pełnych rezerwacji
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą - maksymalny zysk z konferencji, na jaki mogą liczyć organizatorzy.Przykład
Wejście: 3 2 10 30 7 10 8 1 9 3 13 Wyjście: 83
Dla powyższego przykładu, w celu zmaksymalizowania zysków należy wycofać rezerwację trzech biletów z drugiej rezerwacji.
| Dodane przez: | Marcin Sasinowski |
| Data dodania: | 2007-04-18 |
| 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: GOSU |
| Pochodzenie: | Potyczki algorytmiczne 2007 - Runda II [B] |