結果

問題 No.2027 (1, 2, 3, …, N) 's Subset Sum
ユーザー MAHAYANA
提出日時 2023-10-26 00:36:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,003 bytes
コンパイル時間 1,808 ms
コンパイル使用メモリ 178,004 KB
実行使用メモリ 813,956 KB
最終ジャッジ日時 2024-09-25 08:37:45
合計ジャッジ時間 4,071 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,m,n) for(int i=m; i<n; ++i)
#define repl(i,m,n) for(ll i=m; i<n; ++i)

int main(){
    int N; ll S;
    cin >> N >> S;

    vector<ll> A(N);
    rep(i, 0, N) A[i] = ll(i+1);

    vector<vector<bool>> dp(N+1, vector<bool>(S+1, false));
    dp[0][0] = true;

    rep(i, 0, N){
        repl(j, 0, S+1){
            if(!dp[i][j]) continue;
            dp[i+1][j] = true;
            dp[i+1][j+A[i]] = true;
        }
    }

    if(!dp[N][S]){
        cout << -1 << endl;
    }else{
        vector<int> ans;
        ll S2 = S;
        for(int i = N; i > 0; --i){
            if(dp[i-1][S2 - A[i-1]]){
                ans.push_back(A[i-1]);
                S2 -= A[i-1];
            }
        }

        int K = ans.size();
        reverse(ans.begin(), ans.end());
        
        cout << K << endl;
        rep(i, 0, K){
            cout << ans[i];
            cout << (i == K-1 ? '\n' : ' ');
        }
    }

    return 0;
}
0