Cod sursa(job #2775204)

Utilizator loraclorac lorac lorac Data 14 septembrie 2021 21:32:26
Problema Semne Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 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;
const int lim2=15e5+5;
int last[lim2];
void solve()
{
    last[0]=-1;
    int maxim=0;
    for(int i=n;i>=1;--i)
    {
        int pana=maxim;
        for(int j=min(maxim,(int)(sum-v[i]));j>=max(0,(int)(sum-v[i]*i));--j)
        if(last[j]!=0) pana=max(pana,(int)(j+v[i])),
            last[j+v[i]]=i;
        maxim=pana;
        if(maxim==sum)
            break;
    }
    while(sum!=0)
    {
        ans[last[sum]]='-';
        sum-=v[last[sum]];
    }
    for(int i=1;i<=n;++i)
        out<<ans[i];
    out<<'\n';
}
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;
    if(n<=500)
    {
        solve();
        return 0;
    }
    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;
}