問題一覧 > 通常問題

No.1984 [Cherry 4th Tune *] Dilemma

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 27
作問者 : 👑 KazunKazun / テスター : colognecologne potato167potato167
0 ProblemId : 7814 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-17 22:31:43

お知らせ

ジャッジの結果が QLE だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.

問題文

新たな旅立ちを迎えるチェリーちゃんは現在, $N$ 個の目標と $M$ 個の行動と $K$ 個の準備を抱えている. これらはそれぞれ, 目標 $1,2, \dots, N$, 行動 $1,2, \dots, M$, 準備 $1,2, \dots, K$ と名付けられている.

チェリーちゃんはこれらの目標, 行動, 準備の中から1つずつ選び, 順に実行する. なお, 2つ以上同時に実行することはできず, 同じ目標, 行動, 準備を複数回実行することはできない.

$i=1,2, \dots, N$ に対して, 目標 $i$ を達成させるためには, それまでに $L_i$ 個の準備 $A_{i,1}, \dots, A_{i,L_i}$ を全て終えなければならないが, この目標を達成させるとチェリーちゃんは経験値として $E_i$ が得られる.

$j=1,2, \dots, M$ に対して, 行動 $j$ をすると, 経験値として $F_j$ を得る.

$k=1,2, \dots, K$ に対して, 準備 $k$ を終わらせるためにはチェリーちゃんは気力として $V_k$ を消費しなければならない. また, 一度着手した準備は途中で終わらせることはできず, 完遂させなければならない.

そして, $p=1,2, \dots, P$ のそれぞれに対して,

  • 既に目標 $I_p$ を達成しているならば, その後, 行動 $J_p$ をすることはできない.
  • 既に行動 $J_p$ をしているならば, その後, 目標 $I_p$ を達成させることはできない.
ということになっている.

では, 達成させる目標とする行動, 終わらせる準備をうまく選び, 適当な順番で実行し, それらを全て実行し終えたあと, (得られた経験値の総和) $-$ (消費した気力の総和) の最大値とその値になるような行動の方法を1つ求めよ.

ここで, チェリーちゃんは最初は十分な気力を持っているので, 準備の途中で気力切れをしないとする.

制約

  • $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$
  • $p \neq q$ ならば, $(I_p, J_p) \neq (I_q, J_q)$
  • 入力は全て整数である.

入力

$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$

出力

以下の形式で出力せよ.

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

ただし,

  • $C$ は (得られた経験値の総和) $-$ (消費した気力) の最大値
  • $T$ は実行する目標と行動と準備の数の総和
  • ${\rm Motion}_t$ は $t$ 番目に実行する目標や行動, 準備. ただし, 以下のようにして出力せよ.
    • 目標 $i$
      Goal $i$
    • 行動 $j$
      Action $j$
    • 準備 $k$
      Preparation $k$
とする. ただし, 同じ目標や行動, 準備を複数回出力してはいけない.

また, この形式に沿っていない出力に関するジャッジの結果は不定である (WA になるとは限らない).

最後に改行を忘れないこと.

サンプル

サンプル1
入力
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
出力
16
5
Preparation 1
Goal 3
Action 2
Preparation 2
Goal 1

「準備 $1$ を終わらせる $\to$ 目標 $3$ を達成させる $\to$ 行動 $2$ をする $\to$ 準備 $2$ を終わらせる $\to$ 目標 $1$ を達成させる」と実行する.

このとき, 得られた経験値の総和が $E_3+F_2+E_1=19$, 消費した気力の総和が $V_1+V_2=3$ なので, $19-3=16$ となり, これが最大となる.

また, (得られた経験値の総和) $-$ (消費した気力の総和) が $16$ より大きくなるような実行の方法はないので, これは正解となる.

サンプル2
入力
2 2 2 0
1 10
2 20
3 30
0
0
出力
33
4
Goal 1
Action 1
Goal 2
Action 2

$L_i=0$ や $P=0$ の場合がある.

サンプル3
入力
2 1 3 1
1 1
1
46 46 46
3 1 2 3
3 1 2 3
1 1
出力
1
1
Action 1

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