結果

問題 No.15 カタログショッピング
ユーザー ninoinuininoinui
提出日時 2020-07-21 15:45:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 60 ms / 5,000 ms
コード長 1,661 bytes
コンパイル時間 2,674 ms
コンパイル使用メモリ 227,512 KB
実行使用メモリ 14,052 KB
最終ジャッジ日時 2024-06-09 11:24:21
合計ジャッジ時間 3,601 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 49 ms
14,052 KB
testcase_06 AC 56 ms
13,980 KB
testcase_07 AC 55 ms
14,032 KB
testcase_08 AC 56 ms
14,032 KB
testcase_09 AC 60 ms
14,032 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
  long N, S;
  cin >> N >> S;
  vector<long> P(N);
  for (long i = 0; i < N; i++) cin >> P.at(i);
  vector<pair<long, long>> A, B;
  for (long i = 0; i < N; i++) {
    if (i <= N / 2) A.push_back({P.at(i), i + 1});
    else B.push_back({P.at(i), i + 1});
  }
  vector<pair<long, vector<long>>> X;
  for (long bit = 0; bit < 1 << A.size(); bit++) {
    long sum = 0;
    vector<long> tmp;
    for (long i = 0; i < A.size(); i++) {
      if (bit >> i & 1) {
        sum += A.at(i).first;
        tmp.push_back(A.at(i).second);
      }
    }
    X.push_back({sum, tmp});
  }
  vector<pair<long, vector<long>>> Y;
  for (long bit = 0; bit < 1 << B.size(); bit++) {
    long sum = 0;
    vector<long> tmp;
    for (long i = 0; i < B.size(); i++) {
      if (bit >> i & 1) {
        sum += B.at(i).first;
        tmp.push_back(B.at(i).second);
      }
    }
    Y.push_back({sum, tmp});
  }
  sort(Y.begin(), Y.end());
  vector<long> V;
  for (auto [s, v] : Y) V.push_back(s);
  vector<vector<long>> ans;
  for (auto [s, v] : X) {
    if (s > S) continue;
    auto l = lower_bound(V.begin(), V.end(), S - s) - V.begin();
    // if (l == V.end()) continue;
    auto r = upper_bound(V.begin(), V.end(), S - s) - V.begin();
    if (l == r) continue;
    for (long i = l; i < r; i++) {
      vector<long> tmp;
      for (auto a : v) tmp.push_back(a);
      for (auto a : Y.at(i).second) tmp.push_back(a);
      ans.push_back(tmp); 
    }
  }
  sort(ans.begin(), ans.end());
  for (auto a : ans) {
    for (long i = 0; i < a.size(); i++) {
      cout << a.at(i) << ((i == a.size() - 1) ? "\n" : " ");
    }
  }
}
0