Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <regex>
  3. #include <string>
  4. #include <vector>
  5. #include <unordered_set>
  6.  
  7. using namespace std;
  8.  
  9. int solution(const vector<int> &a) {
  10.   int n = a.size();
  11.   int sum = 0;
  12.   for (const int &x : a) {
  13.     sum += x;
  14.   }
  15.   int half = sum / 2;
  16.   int result = 0;
  17.   unordered_set<int> dp[2];
  18.   dp[1].insert(0);
  19.   for (int i = 0; i < n; ++i) {
  20.     for (const int &x : dp[(i + 1) % 2]) {
  21.       dp[i % 2].insert(x);
  22.       int t = x + a[i];
  23.       if (t <= half) {
  24.         result = max(result, t);
  25.         dp[i % 2].insert(t);
  26.       }
  27.     }
  28.     dp[(i + 1) % 2].clear();
  29.   }
  30.   return sum - 2 * result;
  31. }
  32.  
  33. vector<int> toIntVector(string str)
  34. {
  35.   std::vector<int> out;
  36.   std::string i;
  37.   std::istringstream tokenStream(str);
  38.   while (std::getline(tokenStream, i, ','))
  39.   {
  40.     out.push_back(atoi(i.c_str()));
  41.   }
  42.   return out;
  43. }
  44.  
  45. int main()
  46. {
  47.   // Read in from stdin, solve the problem, and write answer to stdout.
  48.   string AS;
  49.   cin >> AS;
  50.   cout << solution(toIntVector(AS));
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement