fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while(t--){
  12.         int n;
  13.         long long k, x;
  14.         cin >> n >> k >> x;
  15.         vector<long long> a(n);
  16.         for (int i = 0; i < n; i++){
  17.             cin >> a[i];
  18.         }
  19.  
  20.         // Compute prefix sums for one block.
  21.         // A[0] = 0, A[i] = a[0] + a[1] + ... + a[i-1] for i>=1.
  22.         vector<long long> A(n+1, 0);
  23.         for (int i = 0; i < n; i++){
  24.             A[i+1] = A[i] + a[i];
  25.         }
  26.         long long S = A[n];  // total sum of one copy of a
  27.         long long total = k * S; // total sum of b
  28.  
  29.         // If the entire array b sums to less than x, then no segment can have sum >= x.
  30.         if(total < x){
  31.             cout << 0 << "\n";
  32.             continue;
  33.         }
  34.  
  35.         // For any starting position l (which corresponds to some block r and index i in [0, n-1]),
  36.         // the prefix sum at that position is r*S + A[i] (with A[0]=0, A[i] for i>=1).
  37.         // We need there to exist an r' (with r'>= current index's block)
  38.         // such that the sum of the segment [l, r'] >= x.
  39.         // Because all numbers are positive, the prefix sum is strictly increasing.
  40.         // The condition is equivalent to:
  41.         //   r*S + A[i] <= total - x.
  42.         // Let tVal = total - x.
  43.         // Then for a fixed remainder index i, we need:
  44.         //   r <= (tVal - A[i]) / S,  with r in [0, k-1].
  45.  
  46.         long long tVal = total - x;
  47.         long long ans = 0;
  48.         for (int i = 0; i < n; i++){
  49.             if(tVal < A[i]) continue;  // no valid block r exists for this remainder
  50.             long long maxR = (tVal - A[i]) / S;
  51.             if(maxR >= k) maxR = k - 1; // ensure r is within [0, k-1]
  52.             ans += (maxR + 1);
  53.         }
  54.  
  55.         cout << ans << "\n";
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
7
5 3 10
3 4 2 1 5
15 97623 1300111
105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
1 100000 1234567891011
1
1 1 1
1
1 1 1
2
2 1 2
1 1
2 1 5
2 1
stdout
copy 
12
1452188
0
1
1
1
0
https://ideone.com/iP07fJ
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!