双指针65pts求hack
查看原帖
双指针65pts求hack
453555
qW__Wp楼主2025/2/3 13:21
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
#define INFF (long long)1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1

using namespace std;

const int N = 1e5 + 5;

int a[N], s[N];
int n, x; 

int get(int l, int r) {
	return s[r] - s[l - 1];
}

int get2(int l, int r) {
	return (r - l + 1) * x;
}

signed main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	cin >> n >> x;
	for (int i = 1; i <= n; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
	int r = 1, ans = s[n];
	for (int l = 1; l <= n; l ++) {
		if (r < l) r = l;
		while (r < n && get(l, r + 1) <= get2(l, r + 1)) r ++;
		ans = max(ans, get(1, l - 1) + get2(l, r) + get(r + 1, n));
//		printf("l = %d, r = %d\n", l, r);
	}
	cout << ans;
	return 0;
}
2025/2/3 13:21
加载中...