asio wybrał się ze znajomymi na majówkę na Mazury. Ekipa podjęła decyzję żeby na wyprawę pojechać jego samochodem. Niestety, w trakcie podróży okazało się, że pogoda jest dość chłodna i Jasio rozważa teraz włączenie klimatyzacji aby podnieść temperaturę w pojeździe.
Układ klimatyzacji jest dość niewygodny w obsłudze. Składa się z N nawiewów ustawionych obok siebie. i-ty z nich ma moc Mi, czyli zwiększa temperaturę w pojeździe o dokładnie Mi stopni Bajcjusza. Czasami moc nawiewu może być ujemna i wtedy zmniejsza on temperaturę w samochodzie.
Na szczęście Jasio ma ze sobą dwie klapy. Dla~każdej z~nich może podjąć decyzję aby jej użyć lub nie. Użycie klapy polega na nałożeniu jej na wybrane przez siebie trzy kolejne nawiewy. Przykryte przez klapę nawiewy przestają zmieniać temperaturę.
Klapy mogą się nakładać na~siebie, ale jeżeli już zostaną użyte, to muszą w całości przykryć jakieś trzy sąsiednie nawiewy (nie jest na przykład możliwe przykrycie tylko dwóch pierwszych nawiewów lub ich częściowe przykrywanie).
Jasio zastanawia się o ile najwięcej stopni Bajcjusza jest w stanie podnieść temperaturę (jeżeli w ogóle opłaca mu się uruchomić klimatyzację).
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę nawiewów w samochodzie Jasia.
W drugim wierszu wejścia znajduje się N liczb całkowitych Mi oznaczających moce kolejnych nawiewów w samochodzie Jasia.
Wyjście
W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca największą możliwą liczbę stopni Bajcjusza, o które może wzrosnąć temperatura w samochodzie Jasia.
Ograniczenia
3 ≤ N ≤ 200 000, − 1 000 000 ≤ Mi ≤ 1 000 000.
Przykład
Input Output Explanation
6
-2 7 -1 -13 2 -7
5
Jasio może użyć obu klap przykrywając sumarycznie cztery nawiewy.
Input Output Explanation
6
-3 0 1000 -3 -6 2
997
Wystarczy użyć jednej klapy do osiągnięcia optymalnego wyniku.
Input Output Explanation
8
-1 -1 -1 -1 -1 -1 -1 -1
0
W tym przypadku nie warto włączać klimatyzacji.
Input Output Explanation
3
2 0 23
25
Jasiowi opłaca się włączyć klimę i nie używać żadnej z klap.
Układ klimatyzacji jest dość niewygodny w obsłudze. Składa się z N nawiewów ustawionych obok siebie. i-ty z nich ma moc Mi, czyli zwiększa temperaturę w pojeździe o dokładnie Mi stopni Bajcjusza. Czasami moc nawiewu może być ujemna i wtedy zmniejsza on temperaturę w samochodzie.
Na szczęście Jasio ma ze sobą dwie klapy. Dla~każdej z~nich może podjąć decyzję aby jej użyć lub nie. Użycie klapy polega na nałożeniu jej na wybrane przez siebie trzy kolejne nawiewy. Przykryte przez klapę nawiewy przestają zmieniać temperaturę.
Klapy mogą się nakładać na~siebie, ale jeżeli już zostaną użyte, to muszą w całości przykryć jakieś trzy sąsiednie nawiewy (nie jest na przykład możliwe przykrycie tylko dwóch pierwszych nawiewów lub ich częściowe przykrywanie).
Jasio zastanawia się o ile najwięcej stopni Bajcjusza jest w stanie podnieść temperaturę (jeżeli w ogóle opłaca mu się uruchomić klimatyzację).
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę nawiewów w samochodzie Jasia.
W drugim wierszu wejścia znajduje się N liczb całkowitych Mi oznaczających moce kolejnych nawiewów w samochodzie Jasia.
Wyjście
W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca największą możliwą liczbę stopni Bajcjusza, o które może wzrosnąć temperatura w samochodzie Jasia.
Ograniczenia
3 ≤ N ≤ 200 000, − 1 000 000 ≤ Mi ≤ 1 000 000.
Przykład
Input Output Explanation
6
-2 7 -1 -13 2 -7
5
Jasio może użyć obu klap przykrywając sumarycznie cztery nawiewy.
Input Output Explanation
6
-3 0 1000 -3 -6 2
997
Wystarczy użyć jednej klapy do osiągnięcia optymalnego wyniku.
Input Output Explanation
8
-1 -1 -1 -1 -1 -1 -1 -1
0
W tym przypadku nie warto włączać klimatyzacji.
Input Output Explanation
3
2 0 23
25
Jasiowi opłaca się włączyć klimę i nie używać żadnej z klap.
Odpowiedź:
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
int best[3] = {0, 1, 2}; // indeksy najlepszych trzech nawiewów
int sum = 0;
for (int i = 0; i < n; i++) {
int m;
cin >> m;
sum += m;
if (m > 0) { // dodatnia moc nawiewu
priority_queue<int, vector<int>, greater<int>> q; // kolejka priorytetowa z najmniejszymi elementami na górze
q.push(best[0]);
q.push(best[1]);
q.push(best[2]);
int j = q.top(); q.pop();
int k = q.top(); q.pop();
int l = q.top(); q.pop();
if (m > sum - best[j] - best[k] - best[l]) {
best[j] = i;
best[k] = j;
best[l] = k;
}
} else if (m < 0) { // ujemna moc nawiewu
priority_queue<int> q; // kolejka priorytetowa z największymi elementami na górze
q.push(best[0]);
q.push(best[1]);
q.push(best[2]);
int j = q.top(); q.pop();
int k = q.top(); q.pop();
int l = q.top(); q.pop();
if (m > sum - best[j] - best[k] - best[l]) {
cout << sum - best[j] - best[k] - best[l] << endl;
return 0;
}
}
}
cout << sum << endl;
return 0;
}