#**HƯỚNG DẪN:**<br>
- Ý tưởng tương tự bài [Chênh lệch nhỏ nhất](https://marisaoj.com/problem/114). Ta vẫn chia đôi tập và sinh tất cả các tổng con của $2$ dãy.<br>
- Tuy nhiên vấn đề là có $mod 10^9.$ Ngăn chặn việc tìm tổng lớn nhất đơn thuần (vì lớn hơn $10^9$ là dư lại về $0$).<<br>
- Xử lý: Ta rút gọn tối đa giá trị các tổng con (chỉ lấy dư cho $10^9$). Khi đó các giá trị cần ghép lại từ $2$ mảng đều $<10^9.$ Nên $0<=a_1[vt1]+a_2[vt2]<2\*10^9$<br>
Với mỗi $a_1[vt1]$ ta có thể chia mảng $a_2$ làm $2$ phần (tổng với $a_1[vt1]$ lớn hơn hoặc nhỏ hơn $10^9$)<br>
$+$ Lớn hơn: Lấy phần tử lớn nhất trong đó (tức là phần tử lớn nhất của cả dãy $a_2$)(có thể phần tử lớn nhất đó cộng với $a_1[vt1]$ bé hơn $10^9$ nhưng ta cứ xét hết vì không ảnh hưởng gì(ứng cử viên cho đáp án))<br>
$+$ Nhỏ hơn: Lấy phần tử lớn nhất trong đó.<br>
$->$ Ta sắp xếp $2$ mảng và dùng thuật toán $2$ con trỏ hoặc tìm kiếm nhị phân để tìm.<br>
##**CODE MẪU:**<br>
```cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<long long> a1,a2;
long long inp[41],ans=-1,sum,mod=1e9;
void sinhtongcon(int i,int r,long long s,vector<long long> &a)
{
if(i>r) a.push_back(s%mod);
else
{
sinhtongcon(i+1,r,s,a);
sinhtongcon(i+1,r,(s+inp[i])%mod,a);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>inp[i];
sinhtongcon(1,n/2,0,a1);
sinhtongcon(n/2+1,n,0,a2);
sort(a1.begin(),a1.end());
sort(a2.begin(),a2.end());
int vt1=0,n1=a1.size(),vt2=a2.size()-1;
int mx=a2[vt2];
while(vt1<n1&&vt2>=0)
{
if(a1[vt1]+a2[vt2]>=mod) vt2--;
else ans=max(ans,max((a1[vt1]+mx)%mod,a1[vt1]+a2[vt2])),vt1++;
}
cout<<ans;
}
```
sharinganvanhoadong
Created at
1 likes