Zadanie Wycinek ILOCAMP

Question

Siema, po długich staraniach udało mi się napisać działający (nie w 100% - inaczej nie pisałbym do Was) kod do zadania Wycinek. Niestety w 3/10 testach jest przekroczenie limitu pamięci.

Moje spostrzerzenia odnośnie tego zadania:

• po pierwsze jeśli choczi o sumę na przedziałach w ciągu, który nie ulega modyfikacjom to tylko i wyłącznie sumy prefiksowe,
• drugim spostrzerzeniem jest to, że żeby otrzymać sumę sum na przedziale [a, b] to DP[b] - DP[a - 1] musi być równe sum, gdzie DP[i] to suma na przedziale [1, i],
• po trzecie jeśli ciąg ma być najdłuższy to jeśli w ciągu np. wystąpiła liczba 3 kilkukrotnie, to opłaca mi się brać tylko to 1. wystąpienie, bo następne tylko pogorszają wynik a następnie szukać elementu sum + 3 w DP[]. Przyda się do tego mapa, gdyż sumy prefiksowe mogą być ujemne,
• gdy już mam przygotowaną tablicę DP[] oraz mapę M[] to żeby znaleźć jakikolwiek ciąg o sumie sum, muszę sprawdzać czy istnieje element M[DP[i] - sum] i od aktualnego i (w pętli for) odjąć indeks, na którym wystąpiła ta liczba.

Prosiłbym o pomoc z tą pamięcią.

Kod: link

Nie podoba mi się ta funkcja find() i podejrzewam, ze to przez nią są te kłopoty.

Answer 1

Wycinek to zadanie co niestety nie wchodzi na mapę. Musisz naliczyć sumy prefiksowe, posortować (bo nie muszą być niemalejące) i napisac wyszukiwanie binarne z każdego elementu. I dostajesz złożonność czasową O(N lg N), i pamięciową O(N)