No.1008 Bench Craftsman
タグ : / 解いたユーザー数 74
作問者 :
Cinnamoroll
/ テスター :
IKyopro
Problem Statement
There is a bench consisting of $N$ sections, and the load capacity of the $i$-th section from the left is $a_i$. It is known that $M$ people will sit on this bench; person $j$ sits on the $x_j$-th section from the left and has a weight of $w_j$.
Letting $c$ be the durability of the bench, the load on the $i$-th section from the left is defined as ${\displaystyle \sum_{j = 1} ^{M} max(0,w_j-abs(i-x_j)·c)}$. The bench breaks if there exists an $i$ such that the $i$-th section from the left bears a load of $a_i$ or more.Also, multiple people may sit on the same section.
Cinnamoroll, a skilled bench craftsman, can change the durability $c$ to any non-negative integer by renovating the bench. Find the minimum durability $c$ required to keep the bench from breaking. If no such $c$ exists, output -1.
Input
$N~~~M$ $a_1~~a_2~~...~~a_N$ $x_1~~w_1$ $x_2~~w_2$ $...$ $x_M~~w_M$
$1 \leq N,M \leq 10^5$
$1 \leq a_i \leq 10^9~~(a_1,a_2,...,a_N)$
$1 \leq x_j \leq N~~~~(x_1,x_2,...,x_M)$
$1 \leq w_j \leq 10^5~~(w_1,w_2,...,w_M)$
All inputs are integers.
Output
Output the minimum required durability. If no durability satisfies the condition, output -1. Print a newline at the end.
Sample
Sample 1
Input
4 3 11 13 12 17 1 8 3 2 4 7
Output
2
When the durability is 0, the loads are (17,17,17,17), and the condition is not satisfied on any section.
When the durability is 1, the loads are (12,13,14,13), and the condition is not satisfied on section 1, section 2, and section 3.
When the durability is 2, the loads are (9,9,11,9), and the condition is satisfied.
Sample 2
Input
5 1 4 6 5 8 2 2 1
Output
0
The durability may be 0.
Sample 3
Input
1 1 1 1 100
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。