%!TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}

\begin{document}

\renewcommand{\tl}{$3$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача AT12. СЛИВАНЕ НА ЖЕЛЕТА}
\addauthor{По задача от 2026 ICPC North America Championship (Dilhan Salgado)}{2026}{06}{24}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 24 юни 2026 г.\\
	Група A
}

Като истински зъл учен, сте усъвършенствали изкуството да създавате все по-големи и по-страховити желета в тайната си лаборатория. Върху кръглата маса в средата на лабораторията са наредени $N$ правоъгълни желета, които образуват \emph{цикличен масив}: те стоят едно до друго в кръг, така че освен обичайните си съседи, и първото, и последното желе също са съседни помежду си. Всяко желе се описва с две цели положителни числа -- \emph{височина} и \emph{ширина}.

По всяко време можете да изберете две съседни желета и да ги \emph{слеете} в едно. Полученото желе има височина, равна на по-голямата от височините на двете слети желета, и ширина, равна на по-голямата от техните ширини. То заема тяхното място в кръга (който вече съдържа с едно желе по-малко) и впоследствие може да бъде сливано със своите съседи наравно с останалите желета.

Лицето на желе с височина $h$ и ширина $w$ е равно на $h \cdot w$. Като извършите няколко (евентуално нула) сливания, искате да направите \textbf{сумата от лицата} на оставащите желета възможно най-голяма. В крайна сметка, колкото по-голямо общо лице покриват желетата Ви, толкова повече градове ще можете да завладеете!

\subsection{Детайли по имплементацията}

Трябва да имплементирате функцията \texttt{solve} със следната сигнатура:
\begin{lstlisting}
 long long solve(std::vector<int> H, std::vector<int> W)
\end{lstlisting}

\begin{itemize}
	\item $H$ и $W$ са вектори с еднаква дължина $N$ ($1 \le N \le 3 \cdot 10^5$);
	\item $H_i$ и $W_i$ ($1 \le H_i, W_i \le 10^6$) са съответно височината и ширината на $i$-тото желе;
	\item желетата са дадени в реда, в който се срещат в кръга;
	\item функцията трябва да върне възможно най-голямата сума от лицата на желетата, която може да бъде постигната след произволен брой сливания.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения} \\
		\hline
		$0$ & $0$  & $-$        & Примерните тестове. \\
		\hline
		$1$ & $10$ & $0$        & $N \le 20$ \\
		\hline
		$2$ & $12$ & $0-1$        & $N \le 500$ \\
		\hline
		$3$ & $15$ & $0-2$     & $N \le 4000$ \\
		\hline
		$4$ & $8$  & $-$        & Всички желета имат еднаква ширина или всички -- еднаква височина. \\
		\hline
		$5$ & $20$ & $-$        & Височините не намаляват, а ширините не нарастват: $h_1 \le \dots \le h_N$ и $w_1 \ge \dots \ge w_N$. \\
		\hline
		$6$ & $35$ & $0-5$ & Няма допълнителни ограничения. \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички нейни тестове, както и тестовете на необходимите ѝ подзадачи.}
\end{table}
\FloatBarrier

\newpage
\subsection{Примери}
\begin{table}[H]
	\small
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{2\\6 3\\2 7}} & \texttt{42} \\
		\hline
		\texttt{\makecell[lt]{4\\1 5\\10 10\\5 1\\6 7}} & \texttt{152} \\
		\hline
		\texttt{\makecell[lt]{5\\6 2\\5 1\\1 5\\2 7\\1 2}} & \texttt{67} \\
		\hline
		\texttt{\makecell[lt]{1\\380385 222650}} & \texttt{84692720250} \\
		\hline
	\end{tblr}
\end{table}

\subsection{Пояснения към примерите}

\noindent\textbf{Първи пример.} Двете желета са с размери $6 \times 3$ и $2 \times 7$ (височина $\times$ ширина). Без нито едно сливане сумата от лицата е $6 \cdot 3 + 2 \cdot 7 = 18 + 14 = 32$. Ако обаче слеем двете желета, получаваме едно желе с височина $\max(6, 2) = 6$ и ширина $\max(3, 7) = 7$, чието лице е $6 \cdot 7 = 42$. По-голяма сума не може да се постигне, затова отговорът е $42$.

\noindent\textbf{Трети пример.} Тук желетата са пет и са подредени в кръг. Един оптимален начин е да ги разделим на две групи от съседни желета:
\begin{itemize}
	\item желета $4$, $5$ и $1$ (те са съседни в кръга, тъй като желе $5$ и желе $1$ са съседни) се сливат в желе с височина $\max(2, 1, 6) = 6$ и ширина $\max(7, 2, 2) = 7$, с лице $6 \cdot 7 = 42$;
	\item желета $2$ и $3$ се сливат в желе с височина $\max(5, 1) = 5$ и ширина $\max(1, 5) = 5$, с лице $5 \cdot 5 = 25$.
\end{itemize}
Общата сума е $42 + 25 = 67$ и това е максималната възможна стойност.

\noindent\textbf{Четвърти пример.} Има само едно желе и не може да се извърши никакво сливане, затова отговорът е просто неговото лице: $380385 \cdot 222650 = 84\,692\,720\,250$.

\FloatBarrier

\subsection{Локален грейдър}

За локално тестване е предоставен грейдър, който чете вход в следния формат:
\begin{itemize}
	\item ред $1$: едно цяло число $N$ -- броят на желетата;
	\item следващите $N$ реда: по две цели числа $H_i$ и $W_i$ -- височината и ширината на $i$-тото желе.
\end{itemize}

Грейдърът извежда върнатата стойност от извикването на \texttt{solve}.

\end{document}
