Cod sursa(job #2775186)

Utilizator loraclorac lorac lorac Data 14 septembrie 2021 20:08:01
Problema Semne Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 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()
{
    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;
    //vector<ll> elim;
    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)
            {
                elim.insert(p.first);
                continue;
            }*/
            if(m.find(p.first+v[i])==m.end())
                need.push_back({p.first+v[i],i});
        }
        //for(auto x:elim)
            //m.erase(m.find(x));
        bool stop=false;
        for(auto p:need)
        {
            m[p.first]=p.second;
            if(p.first==sum)
            {
                stop=true;
                break;
            }
        }
        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;
}