1 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1000009; ll n,k; ll s[N]; struct Info{ ll id,gcd; }; Info f[2][N]; ll sz[2]; ll x[N]; ll GCD(ll a,ll b){ return a%b?GCD(b,a%b):b; } int main(){ freopen("skyline.in","r",stdin); freopen("skyline.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%d",&x[i]); for(int i=1;i<=n;++i)s[i]=s[i-1]+x[i]; ll ans=0; ll now=0; for(int r=1;r<=n;++r){ for(int j=1;j<=sz[now];++j) f[now][j].gcd=GCD(f[now][j].gcd,x[r]); f[now][++sz[now]]=(Info){r,x[r]}; ll nxt=1-now; sz[nxt]=1; f[nxt][1]=f[now][1]; for(int j=2;j<=sz[now];++j) if(f[now][j].gcd!=f[now][j-1].gcd) f[nxt][++sz[nxt]]=f[now][j]; for(int j=1;j<=sz[nxt];++j){ ll l=f[nxt][j].id; if(r-l+1<k) break; ans=max(ans,f[nxt][j].gcd*(s[r]-s[l-1])); } now=nxt; } printf("%lld\n",ans); return 0; }
信息
- ID
- 5
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者