結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2018-11-08 15:43:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,285 bytes |
コンパイル時間 | 2,215 ms |
コンパイル使用メモリ | 200,304 KB |
最終ジャッジ日時 | 2025-01-06 15:53:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}//INSERT ABOVE HEREsigned main(){Int n,x;cin>>n>>x;vector<Int> a(n);for(Int i=0;i<n;i++) cin>>a[i];const Int MAX = 1e4;using P = pair<Int, Int>;vector<P> vp,kp;for(Int i=0;i<n;i++){if(a[i]>=MAX) vp.emplace_back(a[i],i);else kp.emplace_back(a[i],i);}vector<int> dp(n*MAX,-1);dp[0]=n;for(Int i=0;i<(Int)kp.size();i++){for(Int j=n*MAX-1;j>=0;j--){if(dp[j]<0||j+kp[i].first>=n*MAX) continue;if(~dp[j+kp[i].first]) continue;dp[j+kp[i].first]=kp[i].second;}}Int s=1<<vp.size();vector<Int> sm(s,0);vector<int> bs(s,0);for(Int i=0;i<(Int)vp.size();i++) bs[1<<i]=i;for(Int i=1;i<s;i++)sm[i]=sm[i^(i&-i)]+vp[bs[i&-i]].first;for(Int i=0;i<s;i++){Int d=x-sm[i];if(d<0||d>=n*MAX||dp[d]<0) continue;string ans(n,'x');for(Int j=0;j<(Int)vp.size();j++)if((i>>j)&1) ans[vp[j].second]='o';while(dp[d]<n){ans[dp[d]]='o';d-=a[dp[d]];}cout<<ans<<endl;return 0;}cout<<"No"<<endl;return 0;}