# D. Destruction of the Dandelion Fields [문제 링크](https://codeforces.com/contest/2148/problem/D) ## Problem Statement Farmer John has a lawnmower, initially turned off. He also has $n$ fields, with the $i$-th field having $a_i$ dandelions. He will visit all the fields in any order he wants, and each field **exactly once**. FJ's lawnmower seems to have a mind of its own. Right before visiting a field, it checks if the field has an even or odd number of dandelions. If it has an odd number, then the lawnmower toggles its state (if it is off, it turns on; if it is on, it turns off). Then, if the lawnmower is on, it will cut all dandelions in that field. Otherwise, if the lawnmower is off, then FJ will simply visit the field and cut no dandelions. If FJ visits the $n$ fields in optimal order, what is the maximum total number of dandelions he can cut? ## Input The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of fields. The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number of dandelions in each field. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output an integer on a new line: maximum dandelions FJ can cut if he visits all $n$ fields in optimal order. ## 풀이 홀수인 민들레가 있다면 짝수 전부와, 홀수 중 큰 절반을 선택하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<ll> odd, even; while(n--) { ll a; cin >> a; if(a%2) odd.push_back(a); else even.push_back(a); } ll sum=0; if(!odd.empty()) { sum += accumulate(even.begin(), even.end(), 0LL); sort(odd.begin(), odd.end(), greater<ll>()); for(int i=0;i<(odd.size()+1)/2;i++) sum += odd[i]; } cout << sum << '\n'; } } ```