2 条题解

  • 2
    @ 2025-3-29 20:03:20
    #include <cmath>
    using namespace std;
    long long p[1000000],n,a,maxx=-2e18,m,temp[1000000],cnt=0;
    int main() {
    	cin>>n>>m;
    	for(int i=1; i<=n; i++) {
    		cin>>a;
    		//temp[i] = max(temp[i-1] + a, a);
    		if(temp[i-1]+a>a) {
    			cnt++;
    			if(cnt<=m) {
    				temp[i]=temp[i-1]+a;
    				maxx=max(maxx,temp[i]);
    			} else { //1234567
    				//cout<<i<<" "<<cnt<<endl;
    				temp[i-cnt+1]-=temp[i-cnt];// 5 -1 -1 6 -1 -1
    				temp[i-1]-=temp[i-cnt+1];//
    				if(temp[i-1]+a>a) {//把前面的减掉后 仍然大于a 接受前面的转移 否则重新开始新的区间累加 
    					temp[i]=temp[i-1]+a;
                         cnt--;
    					maxx=max(maxx,temp[i]);
    				} else {
    					temp[i]=a;
    					temp[i-1]=0;
    					maxx=max(maxx,temp[i]);
    					cnt=1;
    				}
    			}
    		} else {
    
    			temp[i]=a;
    			temp[i-1]=0;
    			maxx=max(maxx,temp[i]);
    			cnt=1;
    		}
    
    	}
    	cout << maxx<<endl;
    	/*
    5 3
    2 -1 2 9 2 1
    	
    	*/
    	return 0;
    }
    

    信息

    ID
    5054
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者