fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. // #define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) ((a) << (x))
  33. #define div2x(a, x) ((a) >> (x))
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. const int MOD = 1e9 + 7; // 998244353
  52. const int inf = 1e9;
  53. const ll INF = 1e18; // MASK(63) - 1
  54. const int limN = 40 + 5;
  55.  
  56. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  57. ll random(const ll &L, const ll &R) {
  58.     return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. template <class X, class Y>
  62. bool minimize(X &x, const Y &y) {
  63.     return x > y ? x = y, true : false;
  64. }
  65.  
  66. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  67.  
  68.  
  69. int n, a[limN], mid;
  70. ll diff, cnt, dp[MASK(22)];
  71. vector <ll> v1, v2;
  72. unomap <ll, int> mp;
  73. void solve() {
  74.     cin >> n;
  75.     forw (i, 1, n) cin >> a[i];
  76.     if (n == 1) {
  77.         cout << a[1] << " 1\n";
  78.         return;
  79.     }
  80.  
  81.     ll total = 0;
  82.     mid = n >> 1;
  83.     memset(dp, 0, sizeof(dp));
  84.     forw (i, 1, mid) total += a[i];
  85.     forw (mask, 0, MASK(mid) - 1) {
  86.         dp[mask] = dp[mask & (mask - 1)] + a[__builtin_ctz(mask) + 1];
  87.         ll sum = dp[mask] * 2 - total;
  88.         if (!mp.count(sum)) v1.pushb(sum);
  89.         ++mp[sum];
  90.     }
  91.  
  92.     total = 0;
  93.     memset(dp, 0, sizeof(dp));
  94.     forw (i, mid + 1, n) total += a[i];
  95.     forw (mask, 0, MASK(n - mid) - 1) {
  96.         dp[mask] = dp[mask & (mask - 1)] + a[__builtin_ctz(mask) + mid + 1];
  97.         ll sum = dp[mask] * 2 - total;
  98.         v2.pushb(sum);
  99.     }
  100.  
  101.     diff = INF; cnt = 0;
  102.     sort(all(v1)); sort(all(v2), greater <ll> ());
  103.     int i = 0;
  104.     forw (j, 0, sz(v2) - 1) {
  105.         while (i < sz(v1) - 1 && v1[i] <= -v2[j]) ++i;
  106.  
  107.         ll ndiff = abs(v1[i] + v2[j]);
  108.         if (minimize(diff, ndiff)) cnt = mp[v1[i]];
  109.         else if (diff == ndiff) cnt += mp[v1[i]];
  110.  
  111.         if (i) {
  112.             ll ndiff = abs(v1[i - 1] + v2[j]);
  113.             if (minimize(diff, ndiff)) cnt = mp[v1[i - 1]];
  114.             else if (diff == ndiff) cnt += mp[v1[i - 1]];
  115.         }
  116.     }
  117.     cnt >>= 1;
  118.     cout << diff << " " << cnt << endl;
  119. }
  120.  
  121. signed main() {
  122.     ios::sync_with_stdio(false), cin.tie(nullptr);
  123.     srand(time(NULL));
  124.     #define name "test"
  125.     /*
  126.     if (fopen(name".INP", "r")) {
  127.         freopen(name".INP", "r", stdin);
  128.         freopen(name".OUT", "w", stdout);
  129.     }
  130.     */
  131.     bool testCase = false;
  132.     int numTest = 1;
  133.     // cin >> numTest;
  134.     forw (i, 1, numTest) {
  135.         if (testCase) cout << "Case " << i << ": ";
  136.         solve();
  137.     }
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0.01s 36248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/Eaxqf2
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!