Cod sursa(job #2601432)

Utilizator alex_benescuAlex Ben alex_benescu Data 14 aprilie 2020 15:05:05
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[50005], sol[50005];
int calc(int poz,long long s){
  if (s==0)
    return 1;
  if (poz==0)
    return 0;
  if (s>=1LL*v[poz])
    if (calc(poz-1, s-1LL*v[poz])==1){
      sol[poz]=1;
      return 1;
    }
  if(calc(poz-1, s)==1)
    return 1;
  return 0;
}
int main(){
  int n, i;
  long long s, sum=0;
  freopen("semne.in", "r", stdin);
  freopen("semne.out", "w", stdout);
  scanf("%d%lld", &n, &s);
  for(i=1; i<=n; i++)
    scanf("%d", &v[i]), sum=sum+1LL*v[i];
  s=(sum-s)/2;
  calc(n, s);
  for(i=1; i<=n; i++)
    if (sol[i]==1)
      printf("-");
    else
      printf("+");
  return 0;
}