Submission #33816593

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;

template <typename T>
inline void read(T &a) {
	char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
	read(a), read(argv...);
}

int n, l, r;
int a[200000 + 10], /*sufa[200000 + 10], */prefa[200000 + 10];
int choser[200000 + 10];
inline int seca(int l, int r) {
	return prefa[r] - prefa[l - 1];
}
signed main() {
	read(n, l, r);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		prefa[i] = prefa[i - 1] + a[i];
	}
	// for (int i = n; i; --i) {
	// 	sufa[i] = sufa[i + 1] + a[i];
	// }
	for (int i = 1; i <= n; ++i) {
		choser[i] = - seca(i, n) + (n - i + 1) * r;
	}
	// choser[n + 1] = INF;
	for (int i = n; i; --i) {
		choser[i] = min(choser[i], choser[i + 1]);
	}
	int ans = INF;
	for (int i = 0; i <= n; ++i) {
		// ans = min(ans, prefa[n] - seca(1, i) + i * l);
		// ans = min(ans, prefa[n] - seca(i, n) + (n - i + 1) * r);
		ans = min(ans, prefa[n] - seca(1, i) + i * l + choser[i + 1]);
	}
	printf("%lld\n", ans);
}

Submission Info

Judge Result