1 条题解

  • 0
    @ 2024-11-3 21:26:11
    #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;
    }
    
    

    • 1

    信息

    ID
    5
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者