raghuvanshraj

1354.cpp

Jul 30th, 2021
739
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  24.05.2020 12:16:40 AM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long LL;
  10.  
  11. bool isPossible(vector<int> &target) {
  12.     int n = target.size();
  13.     priority_queue<int> max_heap(target.begin(), target.end());
  14.     LL s = accumulate(target.begin(), target.end(), 0LL);
  15.     while (max_heap.top() > s / 2) {
  16.         int curr = max_heap.top();
  17.         max_heap.pop();
  18.         s -= curr;
  19.         if (s <= 1) {
  20.             return s;
  21.         }
  22.  
  23.         max_heap.push(curr % s);
  24.         s += curr % s;
  25.     }
  26.  
  27.     return s == n;
  28. }
  29.  
  30. int main(int argc, char const *argv[]) {
  31.     int n;
  32.     cin >> n;
  33.     vector<int> target(n);
  34.     for (int i = 0; i <= n - 1; ++i) {
  35.         cin >> target[i];
  36.     }
  37.  
  38.     cout << isPossible(target);
  39.  
  40.     return 0;
  41. }
RAW Paste Data