問題一覧 > 通常問題

No.3407 Birds-of-Paradise' Christmas Live

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 15
作問者 : hirayuu_yc / テスター : highlighter
お気に入りにしたユーザー ProblemId : 12876 / 自分の提出
問題文最終更新日: 2025-12-14 10:02:38
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。