Pagini recente » Cod sursa (job #935984) | Cod sursa (job #1797630) | Cod sursa (job #942843) | Cod sursa (job #1185404) | Cod sursa (job #65553)
Cod sursa(job #65553)
using namespace std;
#include <cstdio>
#include <hash_map.h>
#define maxn 50001
int n, s, x[maxn];
hash_map<int, int, hash<int> >dp[maxn];
void afis(int i, int j)
{
if(i==0) return;
if(dp[i][j]==1) { afis(i-1, j-x[i]); printf("+");}
if(dp[i][j]==2) { afis(i-1, j+x[i]); printf("-");}
}
void solve()
{
int i, j;
hash_map<int, int, hash<int> > ::iterator it;
dp[1][x[1]]=1;
dp[1][-x[1]]=2;
for(i=1;i<=n;++i)
for(it=dp[i].begin();it!=dp[i].end();++it)
if(it->first)
dp[i+1][it->first+x[i+1]]=1,
dp[i+1][it->first-x[i+1]]=2;
//for(it=dp[n].begin();it!=dp[n].end();++it)
//printf("%d %d\n", it->first, it->second);
afis(n, s);
}
int main()
{
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%d %d\n", &n, &s);
for(int i=1;i<=n;++i) scanf("%d ", x+i);
solve();
return 0;
}