[Đắk Lắk - TS10 - 2025] Bài 2
Xem dạng PDFCác em đã biết câu chuyện Alibaba và 40 tên cướp. Hôm nay, Alibaba lại vào hang của bọn cướp để lấy vàng. Trong hang có ~N~ (~1 \le N \le 10^5~) túi vàng, trong túi vàng thứ ~i~ (~1 \le i \le N~) có ~a_i~ đồng tiền vàng. Alibaba muốn lấy được số đồng tiền vàng tối đa có thể, đối với mỗi túi vàng Alibaba phải lấy hết số vàng trong túi hoặc không lấy túi đó. Tuy nhiên, lần này để ra khỏi hang, Thần giữ cửa yêu cầu Alibaba chỉ được lấy số lượng đồng tiền vàng là một số chẵn.
Yêu cầu: Tính tổng số đồng tiền vàng tối đa là số chẵn mà Alibaba có thể lấy được. Nếu Alibaba không lấy đồng tiền vàng nào ra khỏi hang coi như tổng số đồng tiền vàng Alibaba lấy là 0.
Input
- Dòng đầu tiên chứa một số nguyên dương ~N~ là số lượng túi vàng trong hang;
- Dòng tiếp theo chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~1 \le a_i \le 10^9, 1 \le i \le N~) lần lượt là số đồng tiền vàng trong mỗi túi, mỗi số cách nhau 1 khoảng trắng.
Output
Xuất ra màn hình một số nguyên duy nhất là tổng số đồng tiền vàng tối đa và là số chẵn mà Alibaba có thể lấy được.
Sample Input 1
4
1 2 3 7
Sample Output 1
12
Giải thích: Trong ví dụ thứ nhất, Alibaba lấy các túi vàng có số đồng tiền vàng tương ứng là ~2 + 3 + 7 = 12~ tối đa và là một số chẵn.
Sample Input 2
3
9999 9999 9999
Sample Output 2
19998
Giải thích: Ví dụ thứ hai, Alibaba lấy 2 túi trong 3 túi vàng, tổng số đồng tiền vàng là ~9999 + 9999 = 19998~ tối đa và là một số chẵn.
Subtasks
- Có 90% số test ứng với 90% số điểm thỏa mãn: ~a_1 + a_2 + ... + a_N~ là số chẵn;
- Có 10% số test còn lại ứng với 10% số điểm: không có ràng buộc gì thêm.
Bình luận
include<bits/stdc++.h>
using namespace std; const int N = 1e6+5; int n, a[N+1]; int main(){ iosbase::syncwith_stdio(false); cin.tie(0);cout.tie(0); cin >> n; long long s = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; s += a[i]; } cout << s; return 0; } nghĩ đơn giản thôi, thế này full rồi
include <bits/stdc++.h>
using namespace std; const int MAXN=1e6+5; long long a[MAXN],pre[MAXN]; int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for (int i=1;i<=n;++i){ cin>>a[i]; }
}