Hỏi ý tưởng bài tập CSES: Two Sets II

[Quoc_Bao_Nguyen1 (Quốc Bảo Nguyễn)]

em xin code với ý tưởng ạ, em dùng qhd mà test ra sai ạ

__Code em ạ:

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int main() {

    // Write C++ code here
    int n, s=0; cin >> n;
    vector <int> a;
    for(int i=1; i<=n; i++){
        s+=i;
        a.push_back(i);
    }
    vector<int> dp(s+1,0);
    dp[0]=1;

    for(int i=0; i<n; i++){
        for(int j=s; j>=a[i]; j--){
            if(dp[j-a[i]]!=0){
                dp[j]++;
            }
           // cout << dp[j] << " ";
        }
       // cout << endl;
    }
    int ans = -1e9;
    for(int i=0; i<=s; i++){
        ans = max(ans,dp[i]);
      //  cout << dp[i] << " ";
    }
   
    int k = 1e9+7;
    cout << (ans/2)%k << endl;

    return 0;
}

[Wipad]

Bạn dùng sai công thức quy hoạch động rồi, nên lấy chút giấy bút ra và nháp lại công thức xem.
Bạn để ý đề bài, tổng dãy số từ 1...n chia ra thành 2 tập hợp có tổng bằng nhau, vậy thì chỉ cần quy hoạch động tới s/2 là ok.
Output cho là in kết quả là số dư của kết quả tìm được với 1E9 + 7, thì cout << ans % (1E9 + 7), à ở mỗi bước tính kết quả cũng cần phải mod đấy.

[Quoc_Bao_Nguyen1 (Quốc Bảo Nguyễn)]

Tại sao (S%2) !=0 thì cout << 0 vậy bạn? Mình seacg thì thấy ngta code như v

[Wipad]

Thì bây giờ đề bài là chia cái dãy 1..n thành 2 dãy có tổng bằng nhau đúng không, vậy thì nếu tổng của dãy 1..n là số lẻ thì bạn có chia được không ?
Ví dụ: 1 2 3 4 5 có tổng bằng 15, bây giờ đố bạn chia cái dãy đó thành 2 dãy với mỗi dãy có tổng bằng 7,5 đấy :))