← 返回 tesla 的题目列表Batched Waypoint Suffix Sum Over 2D Trajectories
类型：online_judge
Given a 3D array traj with shape [batch, num_waypoint, 2], representing a 2D vector at each waypoint for each trajectory.
Compute a suffix-sum scalar sequence along the waypoint dimension. For each b and i:
[ output[b][i] = \sum_{j=i}^{num_waypoint-1} \big(traj[b][j][0] + traj[b][j][1]\big) ]
Return output with shape [batch, num_waypoint].
Input (stdin)
First line: two integers B N (batch size and number of waypoints)
Next B lines: each contains 2*N numbers: x0 y0 x1 y1 ... x{N-1} y{N-1}
Output (stdout)
Print B lines, each with N numbers: the suffix sums for that batch.
Constraints
1 <= B <= 200
1 <= N <= 200000 (overall O(B*N) expected)
Example
Input:
1 4
1 2 3 4 5 6 7 8
Output:
36 33 26 15
Explanation: waypoint scalars are [3,7,11,15], suffix sums are [36,33,26,15].
Example
Input
1 4
1 2 3 4 5 6 7 8
Output
36 33 26 15