No.3407 Birds-of-Paradise' Christmas Live
タグ : / 解いたユーザー数 15
作問者 :
highlighter
Problem Statement
Kanzashi Fuucho and Katakake Fuucho are going to perform a song and dance. How cute. Since their names are really too long, they will be abbreviated as Kanzashi and Katakake from here on.
They dance for $X$ units of time. At time $i$,
- Kanzashi is facing Katakake if and only if $W_i=1$, and
- Katakake is facing Kanzashi if and only if $S_i=1$.
Initially, they remember all of the choreography.
You may perform the operation of making them forget the choreography as many times as you like. Specifically,
- Specify integers $i,j$ with $1\leq i\leq j\leq X$, and one of Kanzashi or Katakake. Here, the specified friend must remember the choreography for times $i,i+1,\dots,j$.
- The specified friend forgets the choreography for times $i,i+1,\dots,j$, and you obtain a reward of $(j-i+1)^2$.
However, you do not wish for the dance to fail. The dance fails if and only if there exists a time satisfying the following condition.
- There is a friend who has forgotten the choreography, and moreover
- that friend is not facing the other friend, or
- the other friend has also forgotten the choreography
Find the maximum reward you can obtain while keeping the dance from failing.
Here, $X,W,S$ are not given directly; instead, you are given a non-negative integer sequence $w$ of length $n$ and a non-negative integer sequence $s$ of length $m$.
$X,W,S$ can be recovered as follows.
- $X$ is the sum of $w$ (note that the sum of $w$ and the sum of $s$ are equal).
- $W$ is the sequence of length $X$ obtained by concatenating, in this order, $w_1$ copies of $1$, $w_2$ copies of $0$, $w_3$ copies of $1$, …, $w_n$ copies of $n\bmod 2$.
- $S$ is the sequence of length $X$ obtained by concatenating, in this order, $s_1$ copies of $1$, $s_2$ copies of $0$, $s_3$ copies of $1$, …, $s_m$ copies of $m\bmod 2$.
Constraints
- $1\leq n,m\leq 3\times 10^5$
- $0\leq w_1,s_1$
- $1\leq w_i$ $(2\leq i\leq n)$
- $1\leq s_i$ $(2\leq i\leq m)$
- $1\leq \sum_{i=1}^{n} w_i=\sum_{i=1}^{m} s_i\leq 10^9$
- All inputs are integers
Input
$n$ $w_1$ $w_2$ $\dots$ $w_n$ $m$ $s_1$ $s_2$ $\dots$ $s_m$
Output
Output the answer.
Sample
Sample 1
Input
2 5 3 3 0 2 6
Output
40
We have $W=(1,1,1,1,1,0,0,0),S=(0,0,1,1,1,1,1,1)$.
It is optimal to make Kanzashi forget the choreography for times $1,2$ and Katakake forget the choreography for times $3,4,\dots,8$; by doing this appropriately, you can obtain a reward of $40$.
Sample 2
Input
4 0 1000000 1 1000000 4 0 1000000 1 1000000
Output
1
I hope these days of getting to meet you go on forever♪
They gaze at each other for just a moment, so it is optimal to make one of them forget the choreography at that moment.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。