题目翻译

长度为 $n$ 的序列 $a$，求 $\max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i$。

$1\leq n\leq 2000,|a_i|\leq 10^6$。

Alice 写了伪代码如下：

function find_answer(n, a)
    # Assumes n is an integer between 1 and 2000, inclusive
    # Assumes a is a list containing n integers: a[0], a[1], ..., a[n-1]
    res = 0
    cur = 0
    k = -1
    for i = 0 to i = n-1
        cur = cur + a[i]
        if cur < 0
            cur = 0
            k = i
        res = max(res, (i-k)*cur)
    return res

给定 $k$ 请你给出一组 hack 满足正确答案比 Alice 的输出大 $k$。

你给出的 hack 也应该满足原题的数据范围限制。

题目思路

Alice 写了个类似最大子段和的东西，但是没有考虑长度带来的影响。换言之，我们让答案区间内包含较少的小负数，但是长度很长，就可以叉掉 Alice。

为了让我们自己方便得到正确答案，我们在最后出现 $2$ 个数，一正一负。

考虑直接构造 $n=2000$ 的情况。

令 $ans$ 表示正确答案，$alice$ 表示 Alice 的答案。我们构造的序列为 $0,0,0,\cdots,0,-x,y$。

然后直接用小学就学过的等式的基本性质推柿子。

首先我们的 $ans=2000(y-x)$，而 Alice 的 $alice=y$ 这个是肯定的。

也就是我们要解出 $2000(y-x)$

那么我们就是要解 $2000(y-x)-y=k$ 这个方程的一个整数解。

移项得到 $y=\frac {2000x+k}{1999}$。

那么我们任取一个 $x$ 不一定满足能整除，那么也就是我们找到的 $x,y$ 必须满足 $2000x+k\equiv 0\pmod{1999}$。减掉 $1999x$ 得到 $x+k\equiv 0\pmod{1999}$。

又因为我们有 $|a_i\leq 10^6|$ 的限制，不能乱找 $x$。保险一点直接取最小的正整数 $x$。即为 $1999-k\bmod {1999}$。

那么我们目前得到了 $1\leq x\leq 1999$，还可以得到 $y=\frac{2000x+k}{1999}=x+\frac{x+k}{1999}\leq 10^6$。

那么做完了。

完整代码

推导过程也写代码里了，duel 的时候手边没有草稿纸是这样的。

#include <bits/stdc++.h>
using namespace std;
int k;
int main()
{
    cin >> k;
    cout << 2000 << endl;
    for (int i = 1; i <= 1998; i++)
        cout << 0 << " ";
    /*
    -x, y
    ans: 2000 * (y - x)
    alice: y
    ans - alice = k
    2000 * (y - x) - y = k
    1999 * y - 2000 * x =k
    y = (2000 * x + k)/1999
    2000 * x % 1999 + k % 1999 = 0 (mod 1999)
    x + k % 1999 = 0 (mod 1999)
    */
    int x = (1999 - k % 1999);
    int y = (2000 * x + k) / 1999;
    cout << -x << " " << y << endl;
    return 0;
}