WA 90 求助！

P2627 [USACO11OPEN] Mowing the Lawn G

rainygame @ 2023-03-04 10:28:44

按照第一篇题解的方法，我写下了如下代码：

#include <stdio.h>
#include <cmath>
#include <string.h>
#define MAXN 100001

inline int uread(){
    int x(0);
    char ch;
    while ((ch = getchar()) < 48);
    do{
        x = (x<<1)+(x<<3)+(ch^48);
    }while ((ch = getchar()) > 47);
    return x;
}

int n, k, s;
long long sum;
long long e[MAXN], f[MAXN+1];

int main(){
    n = uread();
    k = uread();
    for (int i=1; i<=n; i++){
        e[i] = uread();
        sum += e[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;

    for (register int i=1; i<=n+1; ++i){
        s = (i-k-1 > 0 ? i-k-1 : 0);
        for (register int j=s; j<i; ++j) f[i] = (f[i] < f[j] ? f[i] : f[j]);
        f[i] += e[i];
    }

    printf("%lld", sum-f[n+1]);

    return 0;
}

但是，上面的代码只能拿到 90 分（#2WA），请问如何调整？

~~（最后一个点在 999ms 和 1.0s 徘徊……）~~

by rainygame @ 2023-03-04 10:38:01

它#2输出的是负数……

by rainygame @ 2023-03-04 10:44:03

改成 __int128 了，现在是最后一个点 TLE。

#include <stdio.h>
#include <string.h>
#define MAXN 100001

inline int uread(){
    int x(0);
    char ch;
    while ((ch = getchar()) < 48);
    do{
        x = (x<<1)+(x<<3)+(ch^48);
    }while ((ch = getchar()) > 47);
    return x;
}

inline void print(__int128 x){
    __int128 tmp = x/10;
    if (x > 9) print(tmp);
    putchar(x-(tmp<<1)-(tmp<<3)+'0');
}

int n, k, s;
int e[MAXN];
__int128 sum;
__int128 f[MAXN+1];

int main(){
    n = uread();
    k = uread();
    for (int i=1; i<=n; i++){
        e[i] = uread();
        sum += e[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;

    for (register int i=1; i<=n+1; ++i){
        s = (i-k-1 > 0 ? i-k-1 : 0);
        for (register int j=s; j<i; ++j) f[i] = (f[i] < f[j] ? f[i] : f[j]);
        f[i] += e[i];
    }

    print(sum-f[n+1]);

    return 0;
}