Cod sursa(job #1514)
#include <stdio.h>
#include <iostream>
using namespace std;
#define vmax 500000000
#define nmax 50001
int N;
int Stotal, S;
int t[vmax];
int v[vmax];
int a[nmax];
int semne[nmax];
int main()
{
int i = 0, j = 0;
FILE *fin = fopen("semne.in", "rt");
fscanf(fin, "%d %d", &N, &S);
for (i = 1; i <= N; i++)
{
fscanf(fin, "%d", &a[i]);
Stotal += a[i];
}
int Sdif = (Stotal - S) / 2;
fclose(fin);
//cout << Sdif << " " << Stotal << " " << S << '\n';
//cin.get();
v[0] = 1;
for (i = 1; i <= N; i++)
for (j = Sdif; j >= 0; j--)
if (v[j] && j + a[i] <= Sdif)
{
if (v[j + a[i]]) continue;
v[j + a[i]] = 1;
t[j + a[i]] = i;
}
/* for (i = 1; i <= Sdif; i++)
cout << v[i] << ' ';
cout << '\n';
for (i = 1; i <= Sdif; i++)
cout << t[i] << ' ';
cin.get();*/
i = Sdif;
while (i)
{
semne[t[i]] = 1;
i -= a[t[i]];
}
FILE *fout = fopen("semne.out", "wt");
for (i = 1; i <= N; i++)
if (semne[i]) fprintf(fout, "-");
else fprintf(fout, "+");
fclose(fout);
return 0;
}