問題一覧 > 通常問題

No.949 Drinking Programming Contest

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 87
作問者 : りあん / テスター : butsurizuki
お気に入りにしたユーザー ProblemId : 3719 / 自分の提出
問題文最終更新日: 2019-12-10 23:17:08
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
Advent Calendar Contest 2019 (順位表) の他の問題:

Apology

The intended solution got TLE in Python3. We have confirmed that it can get AC when submitted in PyPy3.

Problem Statement

ken and koo have decided to form a team of two and participate in the "Drinking Competitive Programming Contest (Inshu Competitive Programming Contest; ICPC)".

ICPC is a contest consisting of $N$ problems, and the goal is to solve as many problems as possible by performing the following action some number of times.

  • One of the team members drinks. Then, choose 1 problem that has not been solved yet and solve that problem.

Each team member has a fixed contribution: ken's contribution after drinking $i$ times $(0 \le i \le N)$ is $A_i$, and koo's contribution after drinking $i$ times $(0 \le i \le N)$ is $B_i$.

Each problem also has a fixed difficulty: the difficulty of the $i$-th $(1 \le i \le N)$ problem is $D_i$. A problem with difficulty $D_i$ can be solved if the sum of the team members' contributions at that point is at least $D_i$.

Given the contribution of each team member and the difficulty of each problem, find the maximum number of problems that can be solved under an optimal strategy.

Input

$N$
$A_0 \ A_1 \ \ldots \ A_N$
$B_0 \ B_1 \ \ldots \ B_N$
$D_1 \ D_2 \ \ldots \ D_N$

The first line contains an integer $N$, the number of problems.

The second line contains $N+1$ space-separated integers, where the $i+1$-th $(0 \le i \le N)$ integer $A_i$ is the value of ken's contribution immediately after drinking $i$ times.

The third line contains $N+1$ space-separated integers, where the $i+1$-th $(0 \le i \le N)$ integer $B_i$ is the value of koo's contribution immediately after drinking $i$ times.

The fourth line contains $N$ space-separated integers, where the $i$-th $(1 \le i \le N)$ integer $D_i$ is the difficulty of the $i$-th problem.


The input consists of $4$ lines in total and satisfies the following constraints.

  • All input values are integers
  • $1 \le N \le 3{,}000$
  • $-10^5 \le A_i, B_i \le 10^5$
  • $A_{i} \ge A_{i+1}$
  • $B_{i} \ge B_{i+1}$
  • $1 \le D_i \le 2 \times 10^5$

Output

Output the maximum number of problems that can be solved.

Sample

Sample 1
Input
4
5 3 0 -1 -2
5 4 1 0 -3
5 7 4 8
Output
3

For example, 3 problems can be solved by acting as follows.

  • koo drinks. The sum of contributions becomes $5 + 4 = 9$. Then, solve the $4$-th problem.
  • ken drinks. The sum of contributions becomes $3 + 4 = 7$. Then, solve the $1$-st problem.
  • ken drinks. The sum of contributions becomes $0 + 4 = 4$. Then, solve the $3$-rd problem.
Sample 2
Input
5
100 0 -100 -200 -300 -400
8 7 6 5 4 3
5 6 7 8 9
Output
5

By having koo drink every time, all the problems can be solved.

Sample 3
Input
1
1000 -1000
1000 -1000
1
Output
0

Whichever of them drinks, the sum of the team members' contributions becomes less than $1$, so not even 1 problem can be solved.

Sample 4
Input
8
34 8 8 -31 -32 -52 -54 -60 -62
87 71 46 42 8 -2 -35 -41 -52
53 25 15 36 82 79 58 36
Output
6

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