結果

問題 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,285 ms
コンパイル使用メモリ 109,044 KB
実行使用メモリ 10,844 KB
最終ジャッジ日時 2024-06-23 18:17:43
合計ジャッジ時間 2,019 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 41 ms
10,844 KB
testcase_06 AC 45 ms
10,840 KB
testcase_07 AC 47 ms
10,844 KB
testcase_08 AC 45 ms
10,840 KB
testcase_09 AC 45 ms
10,840 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |   scanf("%d%d",&N,&S);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:26:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |   for( int i = 0 ; i <N; i++) scanf("%d", &P[i]);
      |                               ~~~~~^~~~~~~~~~~~~

ソースコード

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