結果

問題 No.332 数列をプレゼントに
ユーザー kroton
提出日時 2015-12-21 02:53:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 1,135 bytes
コンパイル時間 817 ms
コンパイル使用メモリ 65,624 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 07:24:24
合計ジャッジ時間 3,456 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int threshold = 35000;

int main(){
  int N;
  ll X;
  cin >> N >> X;
  vector<pair<int,int>> A, B;
  int Asum = 0;
  for(int i=0;i<N;i++){
    int t;
    cin >> t;
    if(t < threshold){
      A.emplace_back(i, t);
      Asum += t;
    } else {
      B.emplace_back(i, t);
    }
  }
  vector<bool> dp(Asum + 1, false);
  vector<int> pre(Asum + 1, -1);
  dp[0] = true;
  for(int i=0;i<A.size();i++){
    for(int sum=Asum;sum>=A[i].second;sum--)if(!dp[sum] && dp[sum - A[i].second]){
      dp[sum] = true;
      pre[sum] = i;
    }
  }
  for(int m=0;m<1<<B.size();m++){
    ll Bsum = 0;
    for(int i=0;i<B.size();i++)if((m >> i) & 1){
      Bsum += B[i].second;
    }
    if(Bsum > X || X - Bsum > Asum || !dp[X - Bsum])continue;
    string res(N, 'x');
    for(int i=0;i<B.size();i++)if((m >> i) & 1){
      res[B[i].first] = 'o';
    }
    ll rem = X - Bsum;
    while(rem > 0){
      int p = pre[rem];
      res[A[p].first] = 'o';
      rem -= A[p].second;
    }
    cout << res << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}
0