Cod sursa(job #2798386)

Utilizator vladth11Vlad Haivas vladth11 Data 11 noiembrie 2021 11:35:05
Problema Semne Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 50005;
const ll VMAX = 1000005;
const ll INF = (1LL << 55);
const ll MOD = 998244353;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 30;

ll semn[NMAX], n;
ll S;
ll v[NMAX];
int last[NMAX];

int main() {
    ifstream cin("semne.in");
    ofstream cout("semne.out");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll sum = 0;
    cin >> n >> S;
    last[0] = -1;
    for(ll i = 1; i <= n; i++){
        cin >> v[i];
        for(ll j = 0; j <= sum; j++){
            if(!last[j])
                continue;
            last[j + v[i]] = i;
        }
        sum += v[i];
        semn[i] = 1;
    }
    int x = (sum - S) / 2;
    while(last[x] > -1){
        semn[last[x]] = 0;
        x -= v[last[x]];
    }
    for(ll i = 1; i <= n; i++){
        if(semn[i]){
            cout << "+";
        }else{
            cout << "-";
        }
    }
    return 0;
}