[naglowek]

wersja PS     wersja PS.ZIP
Wstęp
Sprawozdanie z przebiegu VII OI
Regulamin
Zasady organizacji zawodów
Informacja o IOI'99
Etap I
Etap II
Etap III
IOI
 
Kwiaciarnia
Kody
Podziemne miasto
Światła drogowe
Spłaszczanie
Pas ziemi
Literatura

Spis treści
O wersji online

Niebieskie książeczki
 
Olimpiada Informatyczna
Kącik zadań
Archiwum zadań
CEOI'97
 
   Krzysztof Diks, Marcin Kubica (przekład)

Kwiaciarnia

Jesteś właścicielem kwiaciarni i przygotowujesz okno wystawowe. Dysponujesz F bukietami kwiatów - każdy innego rodzaju. Masz też do dyspozycji co najmniej tyle samo wazonów, ustawionych w rzędzie na parapecie okna. Wazony są przymocowane na stałe do parapetu i ponumerowane kolejno od 1 do V, gdzie V jest liczbą wazonów. Skrajnie lewy wazon ma numer 1, a skrajnie prawy ma numer V. Bukiety są jednoznacznie ponumerowane od 1 do F. Te numery są ważne z następującego powodu - określają one kolejność występowania bukietów w wazonach. Dla i<j bukiet nr i musi zawsze znajdować się w wazonie położonym na lewo od wazonu, w którym znajduje się bukiet nr j. Np., jeśli azalie mają nr 1, begonie mają nr 2, a cyprysy mają nr 3, to ich bukiety muszą znajdować się w wazonach właśnie w takim porządku - wazon z azaliami musi być na lewo od wazonu z begoniami, a ten na lewo od wazonu z cyprysami. Jeśli mamy więcej wazonów niż bukietów, to nadmiarowe wazony pozostają puste. W każdym wazonie może znajdować się co najwyżej jeden bukiet kwiatów.

Wazony (tak jak bukiety kwiatów) mają swoje charakterystyki. Wkładając bukiet kwiatów do wazonu uzyskujemy określony efekt estetyczny, wyrażany liczbą całkowitą. W tabeli poniżej przedstawiono liczby wyrażające przykładowe efekty estetyczne. W przypadku gdy wazon jest pusty daje to efekt estetyczny równy 0.

ruledtable bf Bukiety | multis...

Zgodnie z powyższą tabelą, azalie wyglądałyby wspaniale w wazonie nr 2, a strasznie w wazonie nr 4.

Dla osiągnięcia najlepszego efektu musisz umieścić bukiety w wazonach, zachowując podany porządek i maksymalizując sumę efektów estetycznych. Jeśli jest kilka takich rozmieszczeń, to każde z nich jest dopuszczalne. Musisz znaleźć jedno z nich.

Założenia

  • 1 le F le 100, gdzie F jest liczbą bukietów kwiatów. Bukiety są ponumerowane od 1 do F.
  • F le V le 100, gdzie V jest liczbą wazonów.
  • -50 le A_ij  le 50, gdzie Aij jest efektem estetycznym umieszczenia i-go bukietu w j-tym wazonie.

Wejście

Nazwą pliku wejściowego jest: flower.inp.

  • Pierwszy wiersz zawiera dwie liczby: F, V.
  • Kolejnych F wierszy ma następującą postać: każdy z nich zawiera V liczb całkowitych - liczba Aij jest j-tą liczbą w (i+1)-ym wierszu.

Wyjście

Plik wyjściowy flower.out musi być plikiem tekstowym i zawierać dwa wiersze:

  • Pierwszy wiersz zawiera sumę efektów estetycznych twojego rozmieszczenia.
  • Drugi wiersz musi zawierać to rozmieszczenie w postaci ciągu F liczb całkowitych, w którym k-ty element jest numerem wazonu zawierającego bukiet nr k.

Przykład

flower.inp:

3 5 
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

flower.out:

53
2 4 5

Ocena

Ograniczenie na czas działania programu wynosi 2 sekundy. Nie można otrzymać części punktów za pojedynczy test.