fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6. void solve() {
  7.     long long t;
  8.     cin >> t;
  9.     while (t--) {
  10.         long long n;
  11.         cin >> n;
  12.         vector<long long> a(n);
  13.         long long specialIndex = -1; 
  14.         for (long long i = 0; i < n; i++) {
  15.             cin >> a[i];
  16.             if (a[i] != 1 && a[i] != -1) {
  17.                 specialIndex = i;
  18.             }
  19.         }
  20.  
  21.         vector<long long> prefixSum(n + 1, 0);
  22.         for (long long i = 0; i < n; i++) {
  23.             prefixSum[i + 1] = prefixSum[i] + a[i];
  24.         }
  25.  
  26.         set<long long> result;
  27.         result.insert(0);
  28.  
  29.         for (long long i = 0; i <= n; i++) {
  30.             for (long long j = i + 1; j <= n; j++) {
  31.                 result.insert(prefixSum[j] - prefixSum[i]);
  32.             }
  33.         }
  34.  
  35.         if (specialIndex != -1) {
  36.             long long x = a[specialIndex];
  37.             for (long long i = 0; i <= specialIndex; i++) {
  38.                 for (long long j = specialIndex + 1; j <= n; j++) {
  39.                     long long sumWithoutX = prefixSum[specialIndex] - prefixSum[i];
  40.                     long long sumWithX = sumWithoutX + x + (prefixSum[j] - prefixSum[specialIndex + 1]);
  41.                     result.insert(sumWithX);
  42.                 }
  43.             }
  44.         }
  45.  
  46.         cout << result.size() << '\n';
  47.         for (long long s : result) {
  48.             cout << s << ' ';
  49.         }
  50.         cout << '\n';
  51.     }
  52. }
  53.  
  54. int main() {
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.     solve();
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
20 
-1 1 -1 1 1 1 1 -1 -1 32 -1 1 1 1 1 1 1 -1 -1 1
stdout
copy 
20
-2 -1 0 1 2 3 4 5 6 29 30 31 32 33 34 35 36 37 38 39
https://ideone.com/hrnHa0
language:
C++ (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!