Zauważ, że po dniach liczba gotówki w automatach będzie się powtarzać, dlatego należy znaleźć maksimum wśród pierwszych dni.
Dla podzadania 1 maksymalna suma będzie albo po pierwszym, albo po drugim dniu, więc możemy po prostu wydobyć maksimum między a n-sum(a).
Dla podzadania 2 wystarczy symulować proces przez pierwsze dni i aktualizować maksimum. Złożoność: O(n \cdot x).
Dla podzadania 3 zauważ, że jeśli żaden z automatów nie zostanie opróżniony, gotówka rośnie liniowo. Automaty będą opróżniane nie więcej niż razy, więc możemy określić te momenty czasowe i symulować proces tylko dla tych momentów. Złożoność: O(n^2).
Dla podzadania 4 możemy symulować proces dla każdego z dni, jednak możemy utrzymywać całkowitą sumę gotówki po każdym dniu, używając formuł i liczby każdego a_i. W tym celu, przechodząc z dnia do dnia i+1, najpierw dodajemy do całkowitej sumy gotówki, a następnie odejmujemy dla każdego automatu, który teraz zawiera dolarów.
Dla ostatniego podzadania musimy połączyć rozwiązania z podzadań 3 i 4.