Untitled

 avatar
meda
c_cpp
19 days ago
1.4 kB
5
Indexable
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;using namespace __gnu_pbds;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
void printff(vector<T>& v) {
  for (auto k : v) cout << k << " ";
  cout << endl;
}
void SOLVE(){
    int n; cin >> n;
    vector<int> a;
    int x; cin >> x;
    a.push_back(x);
    for(int i = 0; i < n - 1; i++){
        char c; cin >> c >> x;
        a.push_back((c == '+' ? x : -x));
    }
    
    int inf = 1e9;
    vector<vector<int>> dp(n, vector<int>(602 * n, -1));
    int offset = n * 300;
    function<int(int, int)> solve =[&] (int i, int sum){
        if(i == n){
            return (sum == 0 ? 0 : inf);
        }
        int &ret = dp[i][sum + offset];
        if(ret != -1) return ret;

        ret = inf;
        ret = min(solve(i + 1, sum + a[i]), solve(i + 1, sum - a[i]) + 1);
        return ret;
    };

    int answer = solve(1, a[0]);
    cout << (answer >= inf ? -1 : answer) << endl;
} 
int main() {
  ios_base::sync_with_stdio(false), cout.tie(nullptr);
  int o_o = 1; //cin >> o_o;
  while(o_o --) SOLVE();
  return 0;
}
Editor is loading...
Leave a Comment