Jak to rozwiązaliście? Rozpisałem ogólne wzorki rekurencyjne dla każdego możliwego typu malowania, np. dla 3 segmentów początkowe 6 możliwości rozwidla się w 2 sztachecie na 3x100, 4x010, 3x001, 5x110, 5x011, 6x111 i kolejne wartości liczą się na podstawie poprzednich, ale to ma w złożoności pamięciowej m*m...

Usprawnienia:

W trakcie wykonywania operacji na liście projektów możemy eliminować projekty gorsze (nielepsze) od innych.

Na przykład dwa projekty: (p1, c1) i (p2, c2) - jeśli p1 <= p2 oraz c1 >= c2 to widzimy, że pierwszy projekt jest gorszy od drugiego (nie dość, że droższy, to jeszcze daje mniejszy bilans energetyczny). A zatem (p1, c1) można usunąć.

To gwarantuje nam, że lista projektów będzie zawierała uporządkowane wpisy (pi, ci), takie że p1 < p2 < p3 < ... oraz c1 < c2 < c3 < ...

Listę projektów przechowywałem w 'map<int, int>' (power jako klucz).

Kolejne usprawnienie dotyczy przepisywania obiektów z jednej listy do drugiej z modyfikacją parametrów. Ponieważ modyfikacja parametrów jest taka sama dla wszystkich projektów, to można zrobić sobie globalne modyfikatory, np:

int deltaPower, deltaCost;

Wtedy wpis w mapie (pi, ci) traktujemy jako (pi + deltaPower, ci + deltaCost).
I zamiast przepisywać wszystkie wpisy zmieniając o (data[i+1], dist(i, i+1)), wystarczy zmodyfikować deltaPower i deltaCost.

Ponadto wyszukiwanie najtańszego nieujemnego projektu możemy zrobić wyszukiwaniem binarnym (a konkretnie lower_bound)

Przy takiej implementacji listy projektów w każdym kroku wykonujemy pojedyncze operacje (wliczając operacje na mapie: lower_bound oraz insert), stąd ostateczna złożoność całego algorytmu to O(n*logn)

Potwierdzam

Potwierdzam, 0.72s.

Obiekty będziemy przeglądać od lewej do prawej.

Dla każdego obiektu 'i' będziemy przechowywać listę potencjalnych projektów sieci energetycznej obejmujących obiekty 0..i. Dla kolejnego obiektu 'i+1' będziemy konstruować taką listę bazując na liście dla obiektu 'i'.

Każdy projekt będzie zakładał, że obiekty od 0 do 'i' są podzielone na autonomiczne energetycznie obszary (spójne składowe sieci). Oczywiście każdy taki obszar musi mieć nieujemny bilans energetyczny. Wyjątkiem jest skrajny prawy obszar (kończący się w obiekcie 'i') - on może zostać rozszerzony do obszaru 'i+1' (lub jeszcze dalej) - dlatego ten obszar może mieć ujemny bilans energetyczny.

W projekcie istotne dla nas będą dwa atrybuty: 'power' oraz 'cost'. Ten drugi to oczywiście koszt, który musimy ponieść aby zrealizować projekt. Z kolei 'power' to bilans energetyczny tego skrajnie prawego obszaru sieci. Nie musimy znać szczegółów na temat zamkniętych obszarów sieci (tych położonych na lewo od ostatniego - niedomkniętego obszaru) - istotne jest tylko to, że koszt ich realizacji jest zagregowany w zmiennej 'cost'.

W jaki sposób sporządzić listę projektów dla obiektu 'i+1'? Mamy dwie możliwości:
- budujemy połączenie od 'i' do 'i+1',
- nie budujemy tego połączenia.

W tym pierwszym przypadku każdy projekt z listy 'i' musimy przenieść na listę 'i+1' uwzględniając poprawki dla planowanego połączenia od 'i' do 'i+1'. A zatem projekt (p, c) przechodzi na (p + data[i+1], c + dist(i, i+1)).

W drugim przypadku odcinamy ostatni obszar sieci i otwieramy nowy obszar. Co do zamykanego właśnie obszaru sieci mamy tylko jedno wymaganie: aby bilans energetyczny był nieujemny. Dlatego w tym miejscu z listy projektów dla 'i' wybieramy najtańszy z nieujemnym 'power'. Do listy projektów dla 'i+1' dodajemy wpis (data[i+1], choosenCost). Oznacza on, że nowo otwarty obszar ma bilans data[i+i], a koszt choosenCost to po prostu koszt realizacji domknięcia poprzedniego obszaru.
Oczywiście drugi przypadek nie zawsze jest możliwy - może się bowiem zdarzyć, że na liście projektów dla 'i' wszystkie projekty mają power < 0.

Po przejrzeniu wszystkich obiektów z listy projektów dla ostatniego wybieramy najtańszy z nieujemnym bilansem.

Algorytm działa O(n*n) - bo dla każdego obiektu przepisujemy całą listę projektów, która w każdym kroku może zostać rozszerzone o jeden element.

O usprawnieniach w kolejnym poście...

Potwierdzam

Potwierdzam, na pierwszym na SIO mam 1.48s.

https://easyupload.io/8nrsb9

Potwierdzam, czas: 0.68s

Potwierdzam

Lokalnie mam 0.55s na obu testach

Potwierdzam

Maciej Hołubowicz, a podzieliłbyś się jaki masz czas dla testów in1.in oraz in2.in (u mnie lokalnie 2.7s. Update: z flagą 03 przechodzi w 0.35s na lapku z i5)? Wyniki mam te same, wykorzystuję 50MB pamięci, a przechodzi mi tylko 5/10 testów i nie wiem o co chodzi :/

Około 1s na dosyć szybkim kompie.

Zakładając, że już w pierwszej fazie obliczyliśmy:
lewo(n) = jak daleko sięga reakcja łańcuchowa w lewo
prawo(n) = jak daleko sięga reakcja łańcuchowa w prawo

Następnie obliczamy:
poprzednia(n) = największe m < n takie, że prawo(m) >= n

Można to zrobić jednym przejściem po minach od lewej do prawej, utrzymując stos min o rosnącym m i malejącym prawo(m).
Jeśli robiliśmy fazę 1 świetną metodą Marcina to mamy to już policzone wcześniej.

I teraz możemy rekurencyjnie obliczyć:
ile(n) = na ile sposobów można pobawić się prefiksem zakończonym miną n
odpalamy(n) = na ile sposobów można pobawić się prefiksem tak, żeby odpalić ostatnią
nie_odpalamy(n) = na ile sposobów można pobawić się prefiksem tak, żeby nie odpalić ostatniej

ile(n) = odpalamy(n) + nie_odpalamy(n)
odpalamy(n) = ile(lewo(n) - 1)
nie_odpalamy(n) = ile(n - 1) - odpalamy(poprzednia(n))