問題一覧 > 通常問題

No.1984 [Cherry 4th Tune *] Dilemma

レベル : / AI推定難易度 : 2175 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 31
作問者 : 👑 Kazun / テスター : 👑 potato167 👑 cologne
お気に入りにしたユーザー ProblemId : 7814 / 自分の提出
問題文最終更新日: 2022-06-17 22:31:43
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
yukicoder contest 348 Early Summer Rain (順位表) の他の問題:

Notice

If the judge result is QLE, there may be an error in the problem or in the judge. Please report it.

Problem Statement

Cherry-chan, who is about to set off on a new journey, currently has $N$ goals, $M$ actions and $K$ preparations. They are named Goal $1,2, \dots, N$, Action $1,2, \dots, M$ and Preparation $1,2, \dots, K$, respectively.

Cherry-chan chooses from among these goals, actions and preparations one at a time and carries them out in order. She cannot carry out two or more at the same time, and she cannot carry out the same goal, action or preparation more than once.

For $i=1,2, \dots, N$, in order to achieve Goal $i$, she must have finished all $L_i$ preparations $A_{i,1}, \dots, A_{i,L_i}$ before then; achieving this goal gives Cherry-chan $E_i$ experience points.

For $j=1,2, \dots, M$, performing Action $j$ gives her $F_j$ experience points.

For $k=1,2, \dots, K$, in order to finish Preparation $k$, Cherry-chan must consume $V_k$ energy. Also, a preparation once started cannot be stopped midway and must be carried through to completion.

Furthermore, for each $p=1,2, \dots, P$, the following hold:

  • If she has already achieved Goal $I_p$, she cannot perform Action $J_p$ afterward.
  • If she has already performed Action $J_p$, she cannot achieve Goal $I_p$ afterward.
These are the rules.

Now, by suitably choosing the goals to achieve, the actions to perform and the preparations to finish, and carrying them out in an appropriate order, find the maximum value of (the total experience points gained) $-$ (the total energy consumed) after all of them have been carried out, and one way of acting that attains this value.

Here, Cherry-chan initially has sufficient energy, so she does not run out of energy in the middle of a preparation.

Constraints

  • $1 \leq N \leq 50$
  • $1 \leq M \leq 50$
  • $1 \leq K \leq 50$
  • $0 \leq P \leq NM$
  • $1 \leq E_i \leq 10^9$
  • $1 \leq F_j \leq 10^9$
  • $1 \leq V_k \leq 10^9$
  • $0 \leq L_i \leq K$
  • $1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,L_i} \leq K$
  • $1 \leq I_p \leq N$
  • $1 \leq J_p \leq M$
  • If $p \neq q$, then $(I_p, J_p) \neq (I_q, J_q)$
  • All inputs are integers.

Input

$N$ $M$ $K$ $P$
$E_1$ $E_2$ $\dots$ $E_N$
$F_1$ $F_2$ $\dots$ $F_M$
$V_1$ $V_2$ $\dots$ $V_K$
$L_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,L_1}$
$L_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,L_2}$
$\vdots$
$L_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,L_N}$
$I_1$ $J_1$
$I_2$ $J_2$
$\vdots$
$I_P$ $J_P$

Output

Output in the following format.

$C$
$T$
${\rm Motion}_1$
${\rm Motion}_2$
$\vdots$
${\rm Motion}_T$

Here,

  • $C$ is the maximum value of (the total experience points gained) $-$ (the energy consumed).
  • $T$ is the total number of goals, actions and preparations carried out.
  • ${\rm Motion}_t$ is the goal, action or preparation carried out $t$-th. Output it as follows:
    • Goal $i$
      Goal $i$
    • Action $j$
      Action $j$
    • Preparation $k$
      Preparation $k$
You must not output the same goal, action or preparation more than once.

The judge result for output that does not follow this format is undefined (it will not necessarily be WA).

Do not forget the newline at the end.

Sample

Sample 1
Input
3 2 4 2
5 7 8
4 6
1 2 3 4
2 1 2
2 2 4
1 2
3 1
2 2
Output
16
5
Preparation 1
Goal 3
Action 2
Preparation 2
Goal 1

She carries out the following: "finish Preparation $1$ $\to$ achieve Goal $3$ $\to$ perform Action $2$ $\to$ finish Preparation $2$ $\to$ achieve Goal $1$".

In this case, the total experience points gained is $E_3+F_2+E_1=19$ and the total energy consumed is $V_1+V_2=3$, so the value is $19-3=16$, which is the maximum.

Also, there is no way of carrying things out that makes (the total experience points gained) $-$ (the total energy consumed) greater than $16$, so this is correct.

Sample 2
Input
2 2 2 0
1 10
2 20
3 30
0
0
Output
33
4
Goal 1
Action 1
Goal 2
Action 2

There may be cases where $L_i=0$ or $P=0$.

Sample 3
Input
2 1 3 1
1 1
1
46 46 46
3 1 2 3
3 1 2 3
1 1
Output
1
1
Action 1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。