fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, a[41], mid;
  5. long long diff, cnt, dp[1 << 20];
  6. vector <long long> v1, v2;
  7. unordered_map <long long, int> mp;
  8. int main() {
  9.     ios::sync_with_stdio(false), cin.tie(nullptr);
  10.     cin >> n;
  11.     for (int i = 1; i <= n; ++i) cin >> a[i];
  12.     if (n == 1) {
  13.         cout << a[1] << " 1\n";
  14.         return 0;
  15.     }
  16.  
  17.     mid = n >> 1;
  18.     long long total = 0;
  19.     for (int i = 1; i <= mid; ++i) 
  20.         total += a[i];
  21.  
  22.     v1.push_back(-total);
  23.     ++mp[-total];
  24.     for (int mask = 1; mask < (1 << mid); ++mask) {
  25.         dp[mask] = dp[mask & (mask - 1)] + a[__builtin_ctz(mask) + 1];
  26.         if (!mp.count(dp[mask] * 2 - total)) v1.push_back(dp[mask] * 2 - total);
  27.         ++mp[dp[mask] * 2 - total];
  28.     }
  29.  
  30.     total = 0;
  31.     for (int i = mid + 1; i <= n; ++i)
  32.         total += a[i];
  33.  
  34.     v2.push_back(-total);
  35.     for (int mask = 1; mask < (1 << (n - mid)); ++mask) {
  36.         dp[mask] = dp[mask & (mask - 1)] + a[__builtin_ctz(mask) + mid + 1];
  37.         v2.push_back(dp[mask] * 2 - total);
  38.     }
  39.  
  40.     diff = 1e18; cnt = 0;
  41.     sort(v1.begin(), v1.end());
  42.     sort(v2.rbegin(), v2.rend());
  43.     int i = 0;
  44.     for (int j = 0; j < v2.size(); ++j) {
  45.         while (i < v1.size() - 1 && v1[i] <= -v2[j]) ++i;
  46.  
  47.         long long ndiff = abs(v1[i] + v2[j]);
  48.         if (diff > ndiff) { diff = ndiff, cnt = mp[v1[i]]; }
  49.         else if (diff == ndiff) cnt += mp[v1[i]];
  50.  
  51.         if (i) {
  52.             ndiff = abs(v1[i - 1] + v2[j]);
  53.             if (diff > ndiff) { diff = ndiff, cnt = mp[v1[i - 1]]; }
  54.             else if (diff == ndiff) cnt += mp[v1[i - 1]];
  55.         }
  56.     }
  57.     cnt >>= 1;
  58.     cout << diff << " " << cnt << "\n";
  59.     return (0 ^ 0);
  60. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
4
1 5 2 3
stdout
copy 
1 2
https://ideone.com/plph5S
language:
C++14 (gcc 8.3)
created:
21 hours 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!