結果
問題 | 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 HERE signed 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; }