結果

問題 No.15 カタログショッピング
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-10 18:13:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 47 ms / 5,000 ms
コード長 2,037 bytes
コンパイル時間 1,907 ms
コンパイル使用メモリ 108,816 KB
実行使用メモリ 10,716 KB
最終ジャッジ日時 2023-09-05 22:56:03
合計ジャッジ時間 2,536 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 44 ms
10,716 KB
testcase_06 AC 44 ms
10,432 KB
testcase_07 AC 47 ms
10,480 KB
testcase_08 AC 47 ms
10,452 KB
testcase_09 AC 47 ms
10,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
int main(){
  int N,S;
  scanf("%d%d",&N,&S);
  int P[N];
  for( int i = 0 ; i <N; i++) scanf("%d", &P[i]);
  vector< pair<int,vector<int> > > p1;
  vector< pair<int,vector<int> > > p2;
  
  for( int i = 0 ; i < (1<<(N/2)); i++ ){
    vector<int> v;
    int sum =0;
    for( int j = 0 ; j < (N/2); j++){
      if( (i&(1<<j))!=0 ){
        v.push_back(j);
        sum+=P[j];
      }
    }
    p1.push_back(make_pair(sum,v));
  }
  for( int i = 0 ; i < (1<<(N-N/2)) ; i++ ){
    vector<int> v;
    int sum =0;
    for( int j = 0 ; j < (N-N/2); j++){
      if( (i&(1<<j))!=0 ){
        v.push_back(N/2+j);
        sum+=P[N/2+j];
      }
    }
    p2.push_back(make_pair(sum,v));
  }
  sort( p2.begin(),p2.end());
  vector< vector<int> > ans;
  for( int i = 0 ; i <(int) p1.size(); i++ ){
    int cost = p1[i].first;
    if( S-cost < 0 ) continue;
    int left = 0;
    int right = p2.size();
    while( left < right ){
      int mid = (left+right)/2;
      if( p2[mid].first < S-cost ){
        left=mid+1;
      }
      else{
        right=mid;
      }
    }
    //cout << cost << ", "<< left <<endl;
    while( left<(int)p2.size() && p2[left].first==S-cost){
      vector<int> ansvec;
      for(int j = 0 ; j < (int)p1[i].second.size(); j++ ){
        ansvec.push_back(p1[i].second[j]);
      }
      for(int j = 0 ; j < (int)p2[left].second.size(); j++ ){
        ansvec.push_back(p2[left].second[j]);
      }
      ans.push_back(ansvec);
      left++;
    }
  }

  sort(ans.begin(),ans.end());
  for( int i = 0 ; i < (int)ans.size(); i++){
    for( int j = 0 ; j < (int)ans[i].size(); j++ ){
      cout << 1+ans[i][j]<<" ";
    }
    cout << endl;
  }
  return 0;
}
0