結果

問題 No.15 カタログショッピング
コンテスト
ユーザー tottoripaper
提出日時 2014-11-16 07:03:33
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,918 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,915 ms
コンパイル使用メモリ 177,952 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 15:58:44
合計ジャッジ時間 2,062 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:11:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |     scanf("%d %d", &N, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:13:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |     for(int i=0;i<N;i++){scanf("%d", ps+i);}
      |                          ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <algorithm>
#include <vector>

typedef std::pair<int,int> P;

int N, S;
int ps[31];

int main(){
    scanf("%d %d", &N, &S);

    for(int i=0;i<N;i++){scanf("%d", ps+i);}
    std::reverse(ps, ps+N);

    std::vector<P> v1, v2;
    for(int i=0;i<(1<<(N/2));i++){
        int sum = 0;
        for(int j=0;j<N/2;j++){
            if(i >> j & 1){
                sum += ps[j];
            }
        }

        if(sum > S){continue;}
        v1.push_back(std::make_pair(sum, i));
    }
    std::sort(v1.begin(), v1.end());

    // for(auto p : v1){printf("v1: %d, %d\n", p.first, p.second);}

    for(int i=0;i<1<<((N+1)/2);i++){
        int i_ = i << (N/2), sum = 0;
        for(int j=N/2;j<N;j++){
            if(i_ >> j & 1){
                sum += ps[j];
            }
        }

        if(sum > S){continue;}
        v2.push_back(std::make_pair(sum, i_));
    }
    std::sort(v2.begin(), v2.end());

    // for(auto p : v2){printf("v2: %d, %d\n", p.first, p.second);}

    std::vector<int> v3;
    int v1_size = v1.size(), v2_size = v2.size();
    for(int i=(int)v1.size()-1,j=0;i>=0;i--){
        P p = v1[i];
        while(j < v2_size && p.first + v2[j].first < S){j += 1;}
        
        int k = j;
        while(j < v2_size && p.first + v2[j].first == S){
            int state = p.second + v2[j].second;
            v3.push_back(state);

            j += 1;
        }

        if(i > 0 && v1[i-1].first == p.first){
            j = k;
        }
    }

    std::sort(v3.begin(), v3.end(), std::greater<int>());
    for(auto state : v3){
        for(int k=N-1;k>=0;k--){
            if((state >> k & 1) == 0){continue;}
                
            if((1 << k) == (state & -state)){
                printf("%d\n", N-k);
            }else{
                printf("%d ", N-k);
            }
        }
    }
}
0