**HINT 1:** Để ý giới hạn $n=1000$. Do đó ta được phép chạy $2$ vòng for. Hãy thử for 2 giá trị nào đó rồi tìm cách check nhanh liệu có cặp số còn lại nào thỏa mãn không?<br>
**HINT 2:** For $2$ giá trị $i,j$ hoặc $k,p$ rồi tìm bộ $2$ vị trí lơn hơn $j$ hoặc nhỏ hơn $k$. Sử dụng map để đánh dấu các tổng đã tồn tại để check nhanh.<br>
#**HƯỚNG DẪN:**<br>
**Cách 1:**
- Chuẩn bị trước map<int,int> mp để lưu các tổng và vị trí lớn nhất của chúng, khi đó nếu xét $mp[k-a[i]-a[j]] <= j$ thì chắc chắn không còn tổng nào có giá trị $k-a[i]-a[j]$ và có $2$ phần tử có vị trí $>j$.<br>
- Chạy các $i,j$ rồi check.
##**Ý TƯỞNG GỐC TẠI BÀI TOÁN SỐ 3 TRONG BÀI VIẾT:** [VNOI WIKI](https://wiki.vnoi.info/algo/basic/meet-in-the-middle.md)<br>
**Cách 2:**
- Chạy các k<p. Rồi kết hợp với đó $1$ map lưu giá trị các tổng của các phần tử có index $<k$.Khi đó không cần bận tâm đến index.<br>
- Cách xây dựng map: <br />
+ Chạy $k$ từ $3->n-1, p$ chạy từ $k+1->n$ (mảng xuất phát từ index $1$).<br>
+ Với mỗi $k,$ ta đã có trước map của các phần tử $1->k-1$ do đó khi $k$ tăng, ta cần cập nhật thêm tổng phần tử $k$ với các phần tử đằng trước.<br>
*Chú ý $mp[...]!=0$ sẽ chậm hơn $mp.count()$ do khi không tìm được thì $mp[...]$ sẽ tự động thêm phần tử $...$ vào làm tăng kích thước.*<br>
##**CODE MẪU:**
```cpp
#include<iostream>
#include<map>
using namespace std;
map<int,int> mp;
int n,k,a[1003];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=3;i<n;i++)
{
for(int j=1;j<i-1;j++)
{
mp[a[j]+a[i-1]]=1;
}
for(int j=i+1;j<=n;j++)
{
if(mp.count(k-a[i]-a[j])) {cout<<"YES";return 0;}
}
}
cout<<"NO";
}
```
sharinganvanhoadong
Created at
1 likes