Explanation

We can turn this into a graph problem, or more precisely, a tree. Let's add an edge from $u$ to $v$ if the maximum length of the subarray that starts at $v$ has to end at $u-1$, and so the next subarray must start at $u$. Remember the array is cyclic, so $u$ is not necessarily greater than $v$. This can be found using basic two pointers. We can iterate through the array with our left pointer and increment our right pointer if the sum between the two pointers is less than or equal to $k$. This will ensure that the subarray starting at the left pointer is as big as possible.

We can use binary lifting for each possible starting position to determine the number of jumps required to cover exactly $n$ elements.

Implementation

Time Complexity: $\mathcal O(n \log n)$

Copy
#include <iostream>

const int MAX_N = 2e5 + 1;
const int LOG = 20;

/*
 * next[i][j] stores the start point of the next
 * 2^j'th subarray if we choose this subarray starting at i
 */
int nxt[2 * MAX_N][LOG];

Copy
MAX_N = 200001
LOG = 20

# next[i][j] stores the start point of the next
# 2^j'th subarray if we choose this subarray starting at i
nxt = [[0] * LOG for _ in range(2 * MAX_N)]

n, k = map(int, input().split())
arr = list(map(int, input().split()))