Sum of Every Subarray
National Olympiad — National round (2026 season)
Submission name: segments.cpp
Problem summary
Find the sum of the sums of all nonempty contiguous subarrays of a sequence of signed integers.
Input
n followed by n integers.
Output
One integer: the total of all contiguous-subarray sums.
Constraints
1 < n ≤ 75000; −1000 < a[i] < 1000. The source allows only 1 MB memory, so read and process each element immediately.
Worked example
Input and output for the worked example discussed below.
Input
4 1 2 3 4
Output
50
Solution analysis
- Instead of enumerating subarrays, reverse the counting. For a fixed 1-based position i, a subarray containing it can start at any position from 1 to i and end at any position from i to n. The independent choices give i(n−i+1) containing subarrays.
- Therefore a[i] contributes a[i]×i×(n−i+1) to the requested sum. Accumulate this contribution as the value is read. Negative elements simply contribute negatively; there is no maximization or empty-subarray exception.
- For [1,2,3,4], the multiplicities are 4,6,6,4. The total is 1×4+2×6+3×6+4×4=50. This matches explicitly summing the ten subarray sums 1,2,3,4,3,5,7,6,9,10.
- No input array or prefix-sum table is needed. The product starts with 1LL to force 64-bit arithmetic before multiplication. The largest possible absolute total is bounded by 999n(n+1)(n+2)/6, below 7.1×10^16.
Why it works
Each occurrence of a[i] in the requested sum corresponds to one unique left/right endpoint pair with left≤i≤right. The formula counts exactly those pairs. Summing all element contributions counts each element of every nonempty subarray exactly once.
Watch out. Do not multiply three int operands before converting to long long. Include singleton subarrays. Do not clamp negative totals to zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cstdio>
int main(){
int n;
if(std::scanf("%d",&n)!=1){
return 0;
}
long long total=0;
for(int i=1;i<=n;i++){
int value;
if(std::scanf("%d",&value)!=1){
return 0;
}
// There are i possible left endpoints and n-i+1 right endpoints.
total+=1LL*value*i*(n-i+1);
}
std::printf("%lld\n",total);
return 0;
}