原题大意

给定一个长度为n的数列A，初始一个变量cnt = 0，每次在0~n里选一个了l和r，然后求出A（l+1）~A（r）的和，将和的绝对值减去常数C，并且加到cnt上，这样的操作最多有m次，求cnt的最大值。

算法分析

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, C;
int a[100005];
ll sum[100005];
bool cmp(ll a, ll b){
    return a > b;
}
int main(){
//freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n >> m >> C){
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        sum[0] = 0;
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + a[i];
        sort(sum, sum+1+n, cmp);
        ll ans = 0;
        for(int i = 0; i < m; i++)
            {
                ans = max(ans, ans + sum[i] - sum[n-i] - C);
            }
        cout << ans << endl;
    }

    return 0;
}