結果

問題 No.15 カタログショッピング
ユーザー ninoinuininoinui
提出日時 2020-07-21 15:45:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 53 ms / 5,000 ms
コード長 1,661 bytes
コンパイル時間 2,703 ms
コンパイル使用メモリ 226,276 KB
実行使用メモリ 14,136 KB
最終ジャッジ日時 2023-08-28 16:13:12
合計ジャッジ時間 3,813 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 48 ms
14,136 KB
testcase_06 AC 51 ms
13,984 KB
testcase_07 AC 53 ms
13,864 KB
testcase_08 AC 52 ms
13,892 KB
testcase_09 AC 52 ms
13,876 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