fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. int main() {
  10.     int N, Q;
  11.     cin >> N >> Q;
  12.     vector<ll> A(N + 1); // 1-based indexing
  13.     vector<ll> prefix_sum(N + 1, 0);
  14.  
  15.     for (int i = 1; i <= N; ++i) {
  16.         cin >> A[i];
  17.     }
  18.  
  19.     sort(A.begin() + 1, A.end()); // Sort the array
  20.     for (int i = 1; i <= N; ++i) {
  21.         prefix_sum[i] = prefix_sum[i - 1] + A[i];
  22.     }
  23.  
  24.     for (int qi = 0; qi < Q; ++qi) {
  25.         ll x;
  26.         cin >> x;
  27.         ll total_sum = 0;
  28.  
  29.         for (int l = 1; l <= N; ++l) {
  30.             // Find the maximum r such that A[l] + A[r] <= x
  31.             ll target = x - A[l];
  32.             int r = upper_bound(A.begin() + l, A.end(), target) - A.begin() - 1;
  33.  
  34.             if (r < l) continue; // No valid r for this l
  35.  
  36.             ll t = r - l + 1;
  37.             ll S = prefix_sum[r] - prefix_sum[l - 1];
  38.             total_sum += (S - A[l] * t);
  39.         }
  40.         cout << total_sum << endl;
  41.     }
  42.  
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5248KB
comments (?)
stdin
copy 
10 4
0 0 0 6 18 18 18 20 20 20
40
19
1
26
stdout
copy 
456
180
0
438
https://ideone.com/ZkAdxa
language:
C++14 (gcc 8.3)
created:
1 year 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!