Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define F first
- #define S second
- #define IDB if (debug)
- typedef long long ll;
- typedef double ld;
- typedef pair <int, int> pii;
- const int SZ = 3e5 + 4;
- const int oo = 1e9 + 4;
- const int mod = 1e9 + 7;
- const bool debug = 0;
- string s;
- ll n, x, t, pr, sum, mn, mx, ok, ans, ind1;
- ll a[SZ], p[SZ], l[SZ];
- ll indmn, indmn2;
- void read() {
- cin >> n >> x;
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- }
- }
- void solve() {
- if (x >= 0) {
- for (int i = 1; i <= n; i++) {
- sum += a[i];
- if (sum < pr) pr = sum;
- ok = max(ok, sum - pr);
- }
- cout << max(ok, ok * x);
- return;
- }
- for (int i = 1; i <= n; i++)
- p[i] = p[i - 1] + a[i];
- for (int i = n; i > 0; i--)
- l[i] = l[i + 1] + a[i];
- pr = 0;
- for (int i = 1; i <= n; i++) {
- pr = min(pr, p[i]);
- p[i] = p[i] - pr;
- // cout << p[i] << ' ';
- }
- //cout << endl;
- pr = 0;
- for (int i = n; i > 0; i--) {
- pr = min(pr, l[i]);
- l[i] = l[i] - pr;
- // cout << l[i] << ' ';
- }
- //cout << endl;
- pr = 0;
- ans = 0;
- sum = 0;
- for (int i = 1; i <= n; i++) {
- sum += a[i];
- if (sum > pr) {
- pr = sum;
- ind1 = i;
- }
- ll ns = (sum - pr) * x + l[i + 1] + p[ind1];
- if (ind1 == i) ns = l[i + 1] + p[ind1];
- // cout << ns << ' ' << sum << ' ' << pr << ' ' << ind1 << ' ' << i <<' ' << p[ind1] << ' ' << l[i + 1] << endl;
- ans = max(ans, ns);
- }
- cout << max(ans, p[n]);
- }
- signed main(){
- ios::sync_with_stdio(0);
- cin.tie(NULL);
- read();
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement