#include <bits/stdc++.h>

using namespace std;
long long a[10009],dp[10009];
int main()
{
    int s;
    cin>>s;
    for(int i=1;i<=s;i++)
    {
        a[i]=i;
    }
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1;i<=s;i++)
    {
        for(int j=s;j>=a[i];j--)
        {

            if(dp[j-a[i]]==1)dp[j]++;
        }
    }
    cout<<dp[s];
    return 0;
}
--------------------------------------------------------------------------------------------------------

Ở đây mình sử dụng thuật toán quy hoạch động của bài toán gốc là Đếm số lượng tập con có tổng bằng S và biến đổi một chút là được =))) còn kiếm test khó hay phức tạp bài này thì chắc là bạn thử lấy bài này của mình xong test với chương trình của bạn thử mấy test lớn lớn á =))))