Skip to Content
CTRL K

Bear and Bowling 4

Explicación

El editorial oficial  usa un enfoque de divide y vencerás. Sin embargo, como muchos problemas de optimización de divide y vencerás, esto también se puede resolver usando el truco de la envolvente convexa.

Primero, definamos lo siguiente:

pre[i]=∑i=1iai \texttt{pre}[i] = \sum_{i = 1}^i a_i ips[i]=∑i=1iai⋅i \texttt{ips}[i] = \sum_{i = 1}^i a_i \cdot i

Queremos encontrar el puntaje de algún subarreglo [l,r][l, r], definido como

∑i=lrai⋅(i−l+1) \sum_{i = l}^r a_i\cdot(i - l+1)

Al expandir esta expresión, podemos expresarla en términos de pre\texttt{pre} y ips\texttt{ips}:

∑i=lrai⋅(i−l+1)=ips[r]−ips[l−1]−(l−1)(pre[r]−pre[l−1]) \sum_{i = l}^r a_i\cdot(i - l+1) = \texttt{ips}[r]-\texttt{ips}[l-1]-(l-1)(\texttt{pre}[r]-\texttt{pre}[l-1])

Para este problema, necesitamos elegir un subarreglo contiguo para maximizar el puntaje requerido. Definamos una función ff tal que f(r)f(r) denota el puntaje máximo de un subarreglo que termina en rr. Así, podemos definir ff de la siguiente forma:

f(r)=max⁡1≤l≤r{ips[r]−ips[l−1]−(l−1)(pre[r]−pre[l−1])}=max⁡1≤l≤r{ips[r]−ips[l−1]−(l−1)pre[r]+(l−1)pre[l−1]}=max⁡1≤l≤r{ips[r]−ips[l−1]−l⋅pre[r]+pre[r]+l⋅pre[l−1]−pre[l−1]}=max⁡1≤l≤r{(ips[l−1]−pre[l−1]+l⋅pre[l−1])−l⋅pre[r]}+ips[r]+pre[r] \begin{align*} f(r) &= \max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - (l - 1)(\texttt{pre}[r] - \texttt{pre}[l - 1])\}\\ &=\max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - (l - 1)\texttt{pre}[r] + (l - 1)\texttt{pre}[l - 1]\}\\ &=\max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - l \cdot \texttt{pre}[r] + \texttt{pre}[r] + l \cdot \texttt{pre}[l - 1] - \texttt{pre}[l - 1]\}\\ &= \max_{1 \leq l \leq r} \{(\texttt{ips}[l - 1] - \texttt{pre}[l - 1] + l \cdot \texttt{pre}[l - 1]) - l \cdot \texttt{pre}[r]\} + \texttt{ips}[r] + \texttt{pre}[r] \end{align*}

Reordenamos la ecuación de modo que los términos que dependen solo de ll queden envueltos entre paréntesis dentro del max⁡\max y los términos que dependen solo de rr se muevan fuera del max⁡\max. Nótese que hay un único término que depende tanto de ll como de rr.

Gracias a esta propiedad, podemos usar el truco de la envolvente convexa. Cada valor se puede representar como una función lineal de la forma

gl(x)=l⋅x+(ips[l−1]−pre[l−1]+l⋅pre[l−1]) g_l(x) = l \cdot x + (\texttt{ips}[l - 1] - \texttt{pre}[l - 1] + l \cdot \texttt{pre}[l - 1])

La ecuación original se puede expresar entonces como:

f(r)=max⁡1≤l≤r{gl(pre[r])}+ips[r]+pre[r] f(r) = \max_{1 \leq l \leq r} \{g_l(\texttt{pre}[r])\} + \texttt{ips}[r] + \texttt{pre}[r]

Implementación

Complejidad: O(nlog⁡n)\mathcal{O}(n \log n). La implementación de abajo usa un Line Container, pero también es posible mantener dinámicamente un deque y usar búsqueda binaria para las consultas aprovechando la monotonía de ll.

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Line Container}
template <typename T> T floor_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
 
struct LineContainerLine {
	mutable long long m, b, p;
	bool operator<(const LineContainerLine &o) const { return m < o.m; }
	bool operator<(long long x) const { return p < x; }
};
 
class LineContainer : multiset<LineContainerLine, less<>> {
	bool isect(iterator x, iterator y) {
		if (y == end()) {
			x->p = LLONG_MAX;
			return false;
		}
		if (x->m == y->m) {
			x->p = x->b > y->b ? LLONG_MAX : LLONG_MIN;
		} else {
			x->p = floor_div(y->b - x->b, x->m - y->m);
		}
		return x->p >= y->p;
	}
 
  public:
	void add(long long m, long long b) {
		auto z = insert({m, b, 0});
		auto y = z++;
		auto x = y;
		while (isect(y, z)) { z = erase(z); }
		if (x != begin() && isect(--x, y)) { isect(x, y = erase(y)); }
		while ((y = x) != begin() && (--x)->p >= y->p) { isect(x, erase(y)); }
	}
 
	long long query(long long x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.m * x + l.b;
	}
};
// EndCodeSnip
 
const int MAXN = 2e5 + 1;
 
int N;
long long A[MAXN], pre[MAXN], ips[MAXN];
 
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		pre[i] = pre[i - 1] + A[i];
		ips[i] = ips[i - 1] + A[i] * i;
	}
 
	LineContainer lc;
	long long ans = 0;
	for (int i = 1; i <= N; i++) {
		lc.add(-i, (i - 1) * pre[i - 1] - ips[i - 1]);
		ans = max(ans, lc.query(pre[i]) + pre[i] + ips[i]);
	}
 
	cout << ans << '\n';
}
Fundamentos