AtCoder Regular Contest 142
翻译中…
Problem Statement
翻译中…
Two wizards, $X$ and $Y$, are fighting with a monster.
翻译中…
Initially, each of the wizards has a magic power of $0$. They know the following two spells.
翻译中…
- Spell
$1$: Increases the caster's magic power by$1$. - Spell
$2$: Deals damage equal to the caster's magic power to the monster.
翻译中…
After each wizard uses a spell $N$ times, they will withdraw from the battle.
For each $i=1, \ldots, N$, they must use one of the following combinations of spells for their $i$-th spells.
翻译中…
$X$casts Spell$a_i$, and$Y$casts Spell$b_i$.$X$casts Spell$c_i$, and$Y$casts Spell$d_i$.
翻译中…
Find the maximum total damage that can be dealt to the monster before the withdrawal.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 8000$$a_i,b_i,c_i,d_i \in \{1,2\}$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
a_1 b_1 c_1 d_1
\vdots
a_N b_N c_N d_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
3
1 1 2 2
2 1 2 2
2 1 1 1
Output #1
3
The maximum total damage can be achieved as follows.
- As the $1$-st spells, use $a_1=1,\, b_1=1$, increasing both $X$'s and $Y$'s magic powers to $1$.
- As the $2$-nd spells, use $c_2=2,\, d_2=2$, dealing $2$ points of damage in total.
- As the $3$-rd spells, use $a_3=2,\, b_3=1$, dealing $1$ point of damage by $X$'s spell and increasing $Y$'s magic power to $2$.
Input #2
5
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
Output #2
0
Casting Spell $2$ with a magic power of $0$ deals no damage.
Input #3
8
1 1 2 2
2 2 2 1
1 1 2 1
1 1 2 2
2 1 1 1
1 2 1 2
2 1 1 2
2 1 2 1
Output #3
20
Input #4
20
2 1 2 1
2 1 1 1
1 2 1 1
2 2 1 2
2 2 2 1
1 1 2 1
1 2 2 2
2 2 2 1
1 1 1 2
1 2 1 2
1 2 2 2
2 1 1 2
2 1 1 1
1 2 1 2
1 2 1 2
1 1 1 2
1 1 2 1
2 2 1 1
1 2 2 2
2 1 1 2
Output #4
138
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。