Untitled
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