AT_arc150_f.[ARC150F] Constant Sum Subsequence

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N^2$ 的正整数序列 $A=(A_1,\ A_2,\ \dots,\ A_{N^2})$ 和一个正整数 $S$ 。对于该正整数序列，满足对于任意正整数 $i\ (1\leq i \leq N^2-N)$ ，都有 $A_i=A_{i+N}$ 。仅给出 $A_1,\ A_2,\ \dots,\ A_N$ 的输入。

请你求出最小的正整数 $L$ ，使得对于任意总和为 $S$ 的正整数序列 $B$ ， $B$ 都是正整数序列 $(A_1,\ A_2,\ \dots,\ A_L)$ 的（不一定连续的）子序列。

在本题的约束条件下，保证这样的 $L$ 至少存在一个。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
6 4
1 1 2 1 4 3
```
输出#1
```
9
```
输入#2
```
14 5
1 1 1 2 3 1 2 4 5 1 1 2 3 1
```
输出#2
```
11
```

输入#3

19 10
1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1

输出#3

说明/提示

约束条件

$1 \leq N \leq 1.5 \times 10^6$
$1 \leq S \leq \min(N, 2 \times 10^5)$
$1 \leq A_i \leq S$
对于任意正整数 $x\ (1\leq x \leq S)$ ， $(A_1,\ A_2,\ \dots,\ A_N)$ 至少包含一个 $x$
输入的所有值均为整数

样例解释 1

需要考虑的 $B$ 包括 $B=(1,1,1,1),\ (1,1,2),\ (1,2,1),\ (1,3),\ (2,1,1),\ (2,2),\ (3,1),\ (4)$ 。例如，当 $L=8$ 时， $B=(2,2)$ 不是 $(A_1,A_2,\dots,A_8)=(1,1,2,1,4,3,1,1)$ 的子序列。而当 $L=9$ 时，所有 $B$ 都是 $(A_1,A_2,\dots,A_9)=(1,1,2,1,4,3,1,1,2)$ 的子序列。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页