1 条题解

  • 1
    @ 2019-01-08 21:01:09
    /*
    单调队列模板题
    然而验题人在做题时用了dp解法
    */
    #define method_1
    #ifdef method_1
    /*
    
    */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=300000+5;
    const int INF=0x3f3f3f3f;
    int n,m;
    int a[maxn],q[maxn];
    int ans=-INF;
    int main() {
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]=a[i-1]+a[i];
        }
        int head=0,tail=0;
        q[head]=0;
        for(int i=1;i<=n;i++){
            while(head<=tail&&q[tail]-q[head]>=m) head++;
            ans=max(ans,a[i]-a[q[head]]);
            while(head<=tail&&a[q[tail]]>=a[i]) tail--;
            q[++tail]=i;
        }
        cout<<ans;
        return 0;
    }
    #endif
    #ifdef method_2
    /*
    
    */
    
    #endif
    #ifdef method_3
    /*
    
    */
    
    #endif
    
    
  • 1

信息

难度
7
分类
(无)
标签
(无)
递交数
212
已通过
35
通过率
17%
被复制
5
上传者