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