Cod sursa(job #65553)

Utilizator gigi_becaliGigi Becali gigi_becali Data 10 iunie 2007 19:28:05
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
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;
}