Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <regex>
- #include <string>
- #include <vector>
- #include <unordered_set>
- using namespace std;
- int solution(const vector<int> &a) {
- int n = a.size();
- int sum = 0;
- for (const int &x : a) {
- sum += x;
- }
- int half = sum / 2;
- int result = 0;
- unordered_set<int> dp[2];
- dp[1].insert(0);
- for (int i = 0; i < n; ++i) {
- for (const int &x : dp[(i + 1) % 2]) {
- dp[i % 2].insert(x);
- int t = x + a[i];
- if (t <= half) {
- result = max(result, t);
- dp[i % 2].insert(t);
- }
- }
- dp[(i + 1) % 2].clear();
- }
- return sum - 2 * result;
- }
- vector<int> toIntVector(string str)
- {
- std::vector<int> out;
- std::string i;
- std::istringstream tokenStream(str);
- while (std::getline(tokenStream, i, ','))
- {
- out.push_back(atoi(i.c_str()));
- }
- return out;
- }
- int main()
- {
- // Read in from stdin, solve the problem, and write answer to stdout.
- string AS;
- cin >> AS;
- cout << solution(toIntVector(AS));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement