38 . 勇者のくせになまいきだ。

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

29.0% (9/31)

Tags

2020 高階競技程式設計 - Contest #3

Description

這是一款在 2007 年 PSP 上推出的遊戲
遊戲內容大略是：
你是魔王所崇拜的破壞神，由於未來會有許多勇者去迷宮中鬧事，所以你必須培養魔物以及設計迷宮去幹掉這些囂張的勇者，以保護住在迷宮中的魔王

但在資源有限的情況下，你除了鞏固迷宮的複雜程度以及魔物的強度，還得考慮這幾天勇者們的出征順序

魔王女兒知道這幾天可能會有哪些勇者闖入迷宮
她告訴你這些勇者的強度 $p_i$ 以及耐力 $s_i$
而你知道勇者們攻擊魔物的順序和魔物們的強度 $a_j$

每天，只會有一位勇者闖入迷宮，他會依序挑戰剩下的魔物 (也就是當已經有 $k$ 個魔物死去，那麼勇者會從第 $k+1$ 個魔物下手)
而勇者與一個魔物決鬥會有兩種結果：

  • 魔物強度比勇者強度還大，勇者死去 (回到重生地 幹)
  • 反之，魔物就會死亡

在魔物被擊敗後，勇者能繼續挑戰下個魔物也可離開迷宮，每挑戰一個魔物就會耗損 $1$ 點耐力，當耐力歸零，勇者會離開迷宮

你得算出勇者最少會花幾天消滅迷宮中的所有魔物，以便設計更好的迷宮

Input Format

第一列給定 $n$ 表示迷宮中有多少魔物 ($1 \le n \le 2\cdot 10^ 5$)
接著依照魔物被攻擊順序有 $n$ 個數字 $a_j$，表示魔物的強度 ($1 \le a_j \le 10^ 9$)

第三列給定 $m$ 表示幾個勇者想闖入迷宮 ($1 \le m \le 2\cdot 10^ 5$)
接著有 $m$ 對數字 $p_i, s_i$ 表示勇者強度以及耐力 ($1 \le p_i \le 10^ 9, 1 \le s_i \le n$)

保證 $n+m \le 2\cdot 10^ 5$

Output Format

輸出一個數字表示勇者最少花幾天能清除迷宮中所有魔物
若沒辦法清除所有魔物則輸出 $-1$

Sample Input 1

6
2 3 7 11 1 8
2
3 2
87 1

Sample Output 1

5

Sample Input 2

5
3 4 99 1 3
2
30 5
87 1

Sample Output 2

-1

Hints

第一筆測資，可能的勇者順序為：
第 $1$ 天：第一個勇者清掉 $2$ 個魔物
第 $2$ 天：第二個勇者清掉 $1$ 個魔物
第 $3$ 天：第二個勇者清掉 $1$ 個魔物
第 $4$ 天：第一個勇者清掉 $1$ 個魔物
第 $5$ 天：第二個勇者清掉 $1$ 個魔物
(再次闖入迷宮的勇者，耐力已經回復至初始值)

隔了十年後出了V!勇者のくせになまいきだR (VR専用)
優良遊戲，各位可以去玩玩看

PIXIV: 63322644

Problem Source

Codeforces 1257D Yet Another Monster Killing Problem

Subtasks

No. Testdata Range Score
1 0~82 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 65536 1
1 500 65536 65536 1
2 500 65536 65536 1
3 500 65536 65536 1
4 500 65536 65536 1
5 500 65536 65536 1
6 500 65536 65536 1
7 500 65536 65536 1
8 500 65536 65536 1
9 500 65536 65536 1
10 500 65536 65536 1
11 500 65536 65536 1
12 500 65536 65536 1
13 500 65536 65536 1
14 500 65536 65536 1
15 500 65536 65536 1
16 500 65536 65536 1
17 500 65536 65536 1
18 500 65536 65536 1
19 500 65536 65536 1
20 500 65536 65536 1
21 500 65536 65536 1
22 500 65536 65536 1
23 500 65536 65536 1
24 500 65536 65536 1
25 500 65536 65536 1
26 500 65536 65536 1
27 500 65536 65536 1
28 500 65536 65536 1
29 500 65536 65536 1
30 500 65536 65536 1
31 500 65536 65536 1
32 500 65536 65536 1
33 500 65536 65536 1
34 500 65536 65536 1
35 500 65536 65536 1
36 500 65536 65536 1
37 500 65536 65536 1
38 500 65536 65536 1
39 500 65536 65536 1
40 500 65536 65536 1
41 500 65536 65536 1
42 500 65536 65536 1
43 500 65536 65536 1
44 500 65536 65536 1
45 500 65536 65536 1
46 500 65536 65536 1
47 500 65536 65536 1
48 500 65536 65536 1
49 500 65536 65536 1
50 500 65536 65536 1
51 500 65536 65536 1
52 500 65536 65536 1
53 500 65536 65536 1
54 500 65536 65536 1
55 500 65536 65536 1
56 500 65536 65536 1
57 500 65536 65536 1
58 500 65536 65536 1
59 500 65536 65536 1
60 500 65536 65536 1
61 500 65536 65536 1
62 500 65536 65536 1
63 500 65536 65536 1
64 500 65536 65536 1
65 500 65536 65536 1
66 500 65536 65536 1
67 500 65536 65536 1
68 500 65536 65536 1
69 500 65536 65536 1
70 500 65536 65536 1
71 500 65536 65536 1
72 500 65536 65536 1
73 500 65536 65536 1
74 500 65536 65536 1
75 500 65536 65536 1
76 500 65536 65536 1
77 500 65536 65536 1
78 500 65536 65536 1
79 500 65536 65536 1
80 500 65536 65536 1
81 500 65536 65536 1
82 500 65536 65536 1
Submit
Status
Ranklist
Back to Top