結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2019-01-22 13:13:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 1,716 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 101,036 KB |
実行使用メモリ | 102,528 KB |
最終ジャッジ日時 | 2024-09-15 13:32:14 |
合計ジャッジ時間 | 7,003 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>using namespace std;typedef long long int ll;typedef pair<ll, int> P;int n; ll x;vector<ll> s1;ll a[101];vector<int> ind1, ind2;ll sum1;ll s2;ll ans1, ans2;bool used2[25];bool used[25];void dfs(int i){if(ans1 || ans2) return;if(i==ind2.size()){if(x-s2<0 || x-s2>sum1) return;int j=lower_bound(s1.begin(), s1.end(), x-s2)-s1.begin();if(s1[j]==x-s2){ans1=s1[j], ans2=s2;for(int j=0; j<ind2.size(); j++) used2[j]=used[j];}return;}dfs(i+1);used[i]=1;s2+=a[ind2[i]];dfs(i+1);used[i]=0;s2-=a[ind2[i]];}int main(){cin>>n>>x;for(int i=0; i<n; i++){cin>>a[i];if(a[i]<=10000) ind1.push_back(i), sum1+=a[i];else ind2.push_back(i);}bool dp[101][1000001];fill(dp[0], dp[0]+sum1+1, 0);dp[0][0]=1;for(int i=1; i<=ind1.size(); i++){int i1=ind1[i-1];for(int j=0; j<=sum1; j++) dp[i][j]=dp[i-1][j];for(int j=a[i1]; j<=sum1; j++) dp[i][j]|=dp[i-1][j-a[i1]];}for(int i=0; i<=sum1; i++) if(dp[ind1.size()][i]) s1.push_back(i);dfs(0);if(ans1==0 && ans2==0){cout<<"No"<<endl;return 0;}char ans[101];int i1=ind1.size();while(i1){if(dp[i1-1][ans1]){ans[ind1[i1-1]]='x';}else{ans1-=a[ind1[i1-1]];ans[ind1[i1-1]]='o';}i1--;}for(int i=0; i<ind2.size(); i++){if(used2[i]) ans[ind2[i]]='o';else ans[ind2[i]]='x';}for(int i=0; i<n; i++) cout<<ans[i];cout<<endl;return 0;}