C++ 解法, 执行用时: 4ms, 内存消耗: 528KB, 提交时间: 2021-11-18

/*
 * @Author: your name
 * @Date: 2021-05-30 09:09:13
 * @LastEditTime: 2021-11-17 16:58:58
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: /zhangtao/Main.cpp
 */ 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
// #define int long long
#define _abs(x) ((x)>0?(x):-(x))
const int maxn=150005;
int n,N,m,a[maxn],lst[maxn],nxt[maxn],tot;
ll ans,b[maxn];
inline void del(int i){
    lst[nxt[i]]=lst[i];
    nxt[lst[i]]=nxt[i];
}
struct data_{
    ll x;int id;
    data_ () {}
    data_(ll _x,int _id):x(_x),id(_id) {}
    bool operator<(const data_&b)const{
        return x>b.x;
    }
};
priority_queue<data_> Q;
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (i==1||(a[i]>0)^(a[i-1]>0)) N++;
        b[N]+=a[i];
    }
    for (int i=1;i<=N;i++){
        lst[i]=i-1;nxt[i]=i+1;
        Q.push(data_(_abs(b[i]),i));
        if (b[i]>0) ans+=b[i],tot++;
    }
    lst[0]=0;nxt[0]=1;lst[N+1]=N;nxt[N+1]=N+1;
    while (tot>m){
        data_ d=Q.top();Q.pop();
        if (lst[nxt[d.id]]!=d.id||nxt[lst[d.id]]!=d.id) continue;
        if (b[d.id]<=0&&(lst[d.id]<1||nxt[d.id]>N)) continue;
        ans-=d.x;tot--;b[d.id]+=b[lst[d.id]]+b[nxt[d.id]];del(lst[d.id]);del(nxt[d.id]);
        Q.push(data_(_abs(b[d.id]),d.id));
    }
    printf("%lld",ans);
    return 0;
}

C++ 解法, 执行用时: 9ms, 内存消耗: 524KB, 提交时间: 2022-04-05

#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<=b;++i) 
using namespace std;
#define vi vector<int>
const int N = 1e5+5;

int n,m;
int a[N],b[N],dp[2][N],mx[2][N];
int main() {
    cin >> n >> m;
    rep(i,1,n) scanf("%d",a+i);
    int tmp = 0;
    rep(i,1,n) {
        if (a[i] == a[i-1]) b[tmp] += a[i];
        else b[++tmp] = a[i];
    }
    n = tmp;
    memcpy(a,b,sizeof(int)*(n+1));

    //rep(i,1,n) cout << a[i] << ' ';
    //cout << endl;
    int c = 1;
    rep(i,1,n) {
        rep(j,1,min(m,i)) {
            dp[c][j] = max(dp[c^1][j],mx[c^1][j-1])+a[i];
            mx[c][j] = max(mx[c^1][j],dp[c][j]);
        }
        c^=1;
    }
    int ans = 0;
    for (int i=1;i<=min(n,m);++i) ans = max(ans,dp[c^1][i]);
    cout << ans << endl;
    return 0;
}