← 返回题目列表

AtCoder · awc0098_d

D. 城市巡回拉力赛

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正在参加一场集会,经过 N 城市。城市已编号 1 通过 N.

这次集会发生于 K 天,从第 1 天到第 1 天 K。高桥每天只呆在一个城市。第一天,他可以选择并留在任何一个 N 城市。从第二天开始,他从前一天停留的城市通过旅行路线移动到另一个城市,并在那里停留。

有 M 城市之间提供出行路线,全部为单程。的 k- 第条路线代表从城市出发的旅行 a_k 前往城市 b_k。使用这条路线可以让他留在城市 b_k 留在城市的第二天 a_k (不一定可以反向行驶)。可以保证 每条路线的 a_k \neq b_k 。

从第2天开始,他只能移动到有从前一天停留的城市出发的旅行路线的城市。由于没有到同城的自环,所以他不能在同一个城市连续停留两天。但是,他可以再次留在同一城市以及中间的其他城市。

各城市 i 有一个基本分数 P_i。居住城市获得的分数 i 当天 j (1 \leq j \leq K) 是 (P_i \times j) \bmod Q。在这里, Q 是给定的正整数,并且 \bmod 表示非负余数。

A 入住计划 为 K days 是长度为城市数字的序列 K, c_1, c_2, \ldots, c_K,满足以下所有条件:

  • 每个 c_j (1 \leq j \leq K) 是介于 1 和 N,包含在内(同一城市号码可能在序列中出现多次)。
  • 对于所有 1 \leq j \leq K - 1,存在一条从城市出发的出行路线 c_j 前往城市 c_{j+1}.

请最大化总分 K 天,即:

\sum_{j=1}^{K} \bigl((P_{c_j} \times j) \bmod Q\bigr)

查找所有有效住宿计划中该金额的最大值。

保证至少存在一个有效的入住计划。

约束

  • 1 \leq N \leq 1000
  • 0 \leq M \leq \min(N \times (N - 1),\; 50000)
  • 1 \leq K \leq 1000
  • 1 \leq Q \leq 10^6
  • 0 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq a_k, b_k \leq N (1 \leq k \leq M)
  • a_k \neq b_k (1 \leq k \leq M)
  • 没有重复的旅行路线(即所有 (a_k, b_k) 是不同的)。
  • 至少有一个有效的入住计划。
  • 所有输入值均为整数。

输入

N M K Q
P_1 P_2 \ldots P_N
a_1 b_1
a_2 b_2
\vdots
a_M b_M
  • 第一行包含城市数量 N,出行路线数量 M, 反弹天数 K,以及正整数 Q 用于分数计算,以空格分隔。
  • 第二行包含城市的基本分数 P_1, P_2, \ldots, P_N,以空格分隔。
  • 的 k- 以下各项 M 行 (1 \leq k \leq M) 包含 a_k 和 b_k 以空格隔开,代表有一条从城市出发的单程出行路线 a_k 前往城市 b_k。如果 M = 0,此部分为空。

输出

打印超过的最大总分 K 天在一行。


示例输入 1

3 3 4 10
2 5 7
1 2
2 3
3 1

示例输出 1

24

示例输入 2

4 5 3 13
4 9 1 7
1 2
1 3
2 4
3 4
4 1

示例输出 2

22

示例输入 3

8 14 10 97
3 14 159 26 535 897 932 38
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1

示例输出 3

606

示例输入 4

15 35 25 1000000
0 999999 123456 789012 345678 901234 567890 234567 890123 456789 111111 222222 333333 444444 555555
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 1
1 5
1 8
2 6
2 9
3 1
3 7
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 1
9 13
9 2
10 14
10 3

示例输出 4

20223100

示例输入 5

1 0 1 1
0

示例输出 5

0