結果

問題 No.15 カタログショッピング
コンテスト
ユーザー ninoinui
提出日時 2020-07-21 15:45:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 5,000 ms
コード長 1,661 bytes
コンパイル時間 4,055 ms
コンパイル使用メモリ 218,820 KB
最終ジャッジ日時 2025-01-12 01:30:31
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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