WA 90分求助

P2627 [USACO11OPEN] Mowing the Lawn G

Forzz_ @ 2023-03-04 11:26:36

#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define U unsigned
#define IL inline
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
const int M=1e5;
int n,m;
int a[N];
int f[N];
deque<int>q;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%lld%lld",&n,&m);
    int sum=0,minn=INF;
    q.push_front(0);
    for(R int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
        while(!q.empty()&&i-q.front()>m+1)
            q.pop_front();
        if(!q.empty())
            a[i]+=a[q.front()];
        while(!q.empty()&&a[q.back()]>=a[i])
            q.pop_back();
        q.push_back(i);
        if(i>=n-m)
            minn=min(minn,a[i]);
    }   
    printf("%lld\n",sum-minn);
    return 0;
}
/*

*/

by george0929 @ 2023-05-29 20:03:28

15行INF初值不够大,要1e17 @Forzz_


|