ГЖО 6 класс 2019

Задача C. Четная сумма

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У Айбара есть $n$ целых чисел. Он хочет выбрать некоторые из них, чтобы получить максимально возможную чётную (то есть, делящуюся на $2$) сумму. Пожалуйста, вычислите, на что может рассчитывать Айбар. Обратите внимание, что если Айбар не выберет ни одного числа, то сумма будет равна чётному числу $0$.

Формат входного файла

В первой строке входных данных записано число $n$ $(1 <= n <= 10^5)$ — количество чисел. В следующей строке записаны $n$ целых чисел, имеющихся у Айбара. Все эти числа не превышают по абсолютному значению $10^9$.

Формат выходного файла

Выведите максимально возможную чётную сумму, которую можно получить, используя каждое из данных чисел не более одного раза.

Примеры:

Вход

3
1 2 3

Ответ

6

Вход

4
1 3 5 -3

Ответ

8

( Aibar Kuanyshbay )

Комментарий/решение

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n, ans=0, b[1] = {2};

cin >> n;

int a[n];

for(int i = 0; i<n; i++){

cin >> a[i];

}

sort(a, a+n);

for(int i = n-1; i>=0; i--){

if(a[i] < 0){

break;

}

ans += a[i];

}

for(int i = 0; i<n; i++){

if(a[i]>0){

if(b[0]>a[i]) b[0]= a[i];

}

}

if(ans %2 == 1){

ans -= b[0];

cout << ans;

}

else{

cout << ans;

}

}

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ll long long

const int MAX = 1e5 + 22;
ll a[MAX];

void solve() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    ll ans = 0;

    for (int i = n - 1; i >= 0; i--) {
        if (a[i] < 0) break;
        ans += a[i];
    }

    if (ans % 2 == 1) {
        ll localMax = 0;
        int plusIdx = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0){
                plusIdx = i;
                break;
            }
            if (abs(a[i]) % 2 == 1) {
                localMax = max(ans + a[i], localMax);
            }
        }
        for (int i = plusIdx; i < n; i++) {
            if (a[i] % 2 == 1) {
                ans -= a[i];
                cout << max(ans, localMax) << '\n';
                return;
            }
        }
    } else {
        cout << ans;
    }
}

int main() {
    int tt = 1; // cin >> tt;
    while(tt--) {
        solve();
    }
}