P16374 [IATI 2026] Arithmetic Progression

Sashka has a sequence $A_0,A_1,\dots,A_{N-1}$ of $N$ positive integers, a positive integer $K$, and an arithmetic progression (A sequence $P_0, P_1,\dots$ is an arithmetic progression if and only if $P_i = D + P_{i-1}$ for all $i \geq 1$ for some constant $D$.), defined by its first element $S$ and the difference between its consecutive elements $D$, which are both positive integers. She is interested in the subsequences (A subsequence of a sequence is obtained by removing zero or more elements from it, without changing the order of the remaining elements.) of length $K$ of $A$ denoted as $B_0, B_1,\dots,B_{K-1}$. Write a program $\texttt{arithmetic\_progression}$ that calculates the minimal sum of respective multiplications of such a subsequence with the first $K$ entries of the arithmetic progression, meaning the following sum is minimized: $$\sum_{i=0}^{K-1} B_i \times (S + i \times D)$$ ### Implementation details You should implement the function $\verb|solve|$: ```cpp __int128 solve(std::vector A, int K, long long S, int D) ``` - $A$: vector, containing $A_0,A_1, \dots, A_{N-1}$ - $K$: the length of the subsequence - $S$: the first entry of the arithmetic progression - $D$: the difference of the arithmetic progression Your function should return the minimal possible sum of the described type. As it may be too large, your function should return the variable of the non-standard $\texttt{\_\_int128}$ type for $128$ bit integers. The header file $\texttt{arithmetic\_progression.h}$ contains overloaded definitions for the $\texttt{}$ operators, allowing the use of $\verb|std::cin|$, $\verb|std::cout|$ and $\verb|std::cerr|$ for $\verb|__int128|$ variables.

Input format: - line 1: $N$ $K$ $S$ $D$; - line 2: $A_0\ A_1\ A_2\ ...\ A_{N-1}$.

Output format: - line 1: one integer, equal to the answer returned by \verb|solve|

### Comment 1 The arithmetic progression is $\{1,2\}$. We choose $B=\{5,1\}$, and we get the optimal result: $5 \times 1 + 1 \times 2 = 7$ ### Comment 2 The arithmetic progression is $\{6,7\}$. We choose $B=\{1,4\}$, and we get the optimal result: $1 \times 6 + 4 \times 7 = 34$ ### Comment 3 The arithmetic progression is $\{4,10,16,22\}$. We choose $B=\{18,12,8,11\}$, and we get the optimal result: $18 \times 4 + 12 \times 10 + 8 \times 16 + 11 \times 22 = 562$ ### Constraints - $1 \leq K \leq N \leq 300\ 000$ - $1 \leq D \leq 10^9$ - $1 \leq A_i, S \leq 10^{15}$ ### Subtasks | **Subtask** | **Points** | **Required subtasks** | **$N$** | **Other constraints** | | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | The sample tests. | | $1$ | $5$ | $0$ | $\leq 20$ | $-$ | | $2$ | $6$ | $0-1$ | $\leq 500$ | $-$ | | $3$ | $3$ | $0-2$ | $\leq 3\ 000$ | $-$ | | $4$ | $1$ | $-$ | $\leq 100\ 000$ | $K = N$ | | $5$ | $4$ | $4$ | $\leq 100\ 000$ | $K \geq N - 1$ | | $6$ | $4$ | $4-5$ | $\leq 100\ 000$ | $K \geq N-2$ | | $7$ | $5$ | $-$ | $\leq 100\ 000$ | $A$ is obtained by uniformly shuffling a sequence $T$ that is chosen by the author for the given test. | | $8$ | $5$ | $0-7$ | $\leq 100\ 000$ | $-$ | | $9$ | $67$ | $0-8$ | $\leq 300\ 000$ | $-$ | The points for a given subtask are obtained only if all the tests for it and the required subtasks are successfully passed.