1 条题解
-
1yejun LV 10 MOD @ 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
- 上传者