Cod sursa(job #2775189)

Utilizator loraclorac lorac lorac Data 14 septembrie 2021 20:29:54
Problema Semne Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
typedef long long ll;
const ll lim=5e4+5;
map<ll,ll> m;
char ans[lim];
ll v[lim];
ll n,diff,sum;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    in>>n>>diff;
    for(ll i=1;i<=n;++i)
        in>>v[i],sum+=v[i],ans[i]='+';
    sum=(sum-diff)/2;
    m[0]=-1;
    vector<pair<ll,ll> > need;
    for(ll i=n;i>=1;--i)
    {
        need.clear();
        for(auto p:m)
        {
            if(p.first+v[i]>sum)
                break;
            if(p.first+v[i]*i<sum)
                continue;
            if(m.find(p.first+v[i])==m.end())
                need.push_back({p.first+v[i],i});
        }
        bool stop=false;
        for(auto p:need)
        {
            m[p.first]=p.second;
            if(p.first==sum)
            {
                stop=true;
                break;
            }
        }
        need.clear();
        if(stop) break;
    }
    while(sum!=0)
    {
        ans[m[sum]]='-';
        sum-=v[m[sum]];
    }
    for(ll i=1;i<=n;++i)
        out<<ans[i];
    out<<'\n';
    return 0;
}