90分,第八个点莫名错误,求助

P2627 [USACO11OPEN] Mowing the Lawn G

xyxyfqbj @ 2020-04-11 13:47:18

 #include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N], sum = 0, f[N];
int n, m, q[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        sum += s[i];
    }
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++)
    {
        while (hh <= tt && i - q[hh] > m + 1) hh++;
        f[i] = f[q[hh]] + s[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[ ++ tt] = i;
    }
    LL res = 0x7fffffff;
    for (int i = n - m; i <= n; i++)
    {
        res = min(res, f[i]);
    }
    cout << sum - res << endl;
    return 0;
}

WA在第8个点了


by 㔿㕛㠪䦹冎 @ 2020-08-21 17:10:27

res 初始值不够大


by _l_l_l_l_l_ @ 2021-08-04 18:38:55

@xyxyfqbj 建议res开到1e16


by william_zy @ 2022-11-19 20:16:26

可以试着强行推 f[n+1] ,输出 sum-f[n+1] ?我就是这么莫名 AC


|