{"problem":{"name":"C. Annoying Present","description":{"content":"Alice got an array of length $n$ as a birthday present once again! This is the third year in a row! And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decide","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1009C"},"statements":[{"statement_type":"Markdown","content":"Alice got an array of length $n$ as a birthday present once again! This is the third year in a row!\n\nAnd what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.\n\nBob has chosen $m$ changes of the following form. For some integer numbers $x$ and $d$, he chooses an arbitrary position $i$ ($1 \\le i \\le n$) and for every $j \\in [1, n]$ adds $x + d \\cdot dist(i, j)$ to the value of the $j$\\-th cell. $dist(i, j)$ is the distance between positions $i$ and $j$ (i.e. $dist(i, j) = |i - j|$, where $|x|$ is an absolute value of $x$).\n\nFor example, if Alice currently has an array $[2, 1, 2, 2]$ and Bob chooses position $3$ for $x = -1$ and $d = 2$ then the array will become $[2 - 1 + 2 \\cdot 2,~1 - 1 + 2 \\cdot 1,~2 - 1 + 2 \\cdot 0,~2 - 1 + 2 \\cdot 1]$ = $[5, 2, 1, 3]$. Note that Bob can't choose position $i$ outside of the array (that is, smaller than $1$ or greater than $n$).\n\nAlice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.\n\nWhat is the maximum arithmetic mean value Bob can achieve?\n\n## Input\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n, m \\le 10^5$) — the number of elements of the array and the number of changes.\n\nEach of the next $m$ lines contains two integers $x_i$ and $d_i$ ($-10^3 \\le x_i, d_i \\le 10^3$) — the parameters for the $i$\\-th change.\n\n## Output\n\nPrint the maximal average arithmetic mean of the elements Bob can achieve.\n\nYour answer is considered correct if its absolute or relative error doesn't exceed $10^{-6}$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Alice 再次收到了一个长度为 $n$ 的数组作为生日礼物！这已经是连续第三年了！\n\n更令人失望的是，这个数组极其无聊，全部由零组成。Bob 决定对数组进行一些修改，以让 Alice 开心起来。\n\nBob 选择了 $m$ 次如下形式的修改。对于某些整数 $x$ 和 $d$，他选择一个任意位置 $i$（$1 lt.eq i lt.eq n$），并对每个 $j in [ 1, n ]$，将 $x + d dot.op d i s t (i, j)$ 加到第 $j$ 个单元格的值上。$d i s t (i, j)$ 是位置 $i$ 和 $j$ 之间的距离（即 $d i s t (i, j) = | i -j |$，其中 $| x |$ 表示 $x$ 的绝对值）。\n\n例如，如果 Alice 当前的数组是 $[ 2, 1, 2, 2 ]$，而 Bob 选择位置 $3$，并令 $x = -1$、$d = 2$，则数组将变为 $[ 2 -1 + 2 dot.op 2, med 1 -1 + 2 dot.op 1, med 2 -1 + 2 dot.op 0, med 2 -1 + 2 dot.op 1 ]$ = $[ 5, 2, 1, 3 ]$。注意，Bob 不能选择超出数组范围的位置（即小于 $1$ 或大于 $n$）。\n\n当数组中的元素尽可能大时，Alice 会最快乐。Bob 认为元素的算术平均值是一个合适的度量标准。\n\nBob 能达到的最大算术平均值是多少？\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 10^5$）——数组的元素个数和修改次数。\n\n接下来的 $m$ 行每行包含两个整数 $x_i$ 和 $d_i$（$-10^3 lt.eq x_i, d_i lt.eq 10^3$）——第 $i$ 次修改的参数。\n\n请输出 Bob 能达到的最大算术平均值。\n\n你的答案若绝对误差或相对误差不超过 $10^(-6)$，则被视为正确。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n, m lt.eq 10^5$）——数组的元素个数和修改次数。接下来的 $m$ 行每行包含两个整数 $x_i$ 和 $d_i$（$-10^3 lt.eq x_i, d_i lt.eq 10^3$）——第 $i$ 次修改的参数。\n\n## Output\n\n请输出 Bob 能达到的最大算术平均值。你的答案若绝对误差或相对误差不超过 $10^(-6)$，则被视为正确。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the length of the array and the number of changes, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the array, initially $ a_j = 0 $ for all $ j \\in \\{1, \\dots, n\\} $.  \nFor each change $ i \\in \\{1, \\dots, m\\} $, Bob selects a position $ p_i \\in \\{1, \\dots, n\\} $ and adds to each element $ a_j $ the value:  \n$$\nx_i + d_i \\cdot |p_i - j|\n$$\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 10^5 $  \n2. $ -10^3 \\le x_i, d_i \\le 10^3 $ for all $ i \\in \\{1, \\dots, m\\} $  \n3. For each change $ i $, the position $ p_i $ is chosen optimally from $ \\{1, \\dots, n\\} $ to maximize the final average.\n\n**Objective**  \nMaximize the arithmetic mean of the final array:  \n$$\n\\max_{p_1, \\dots, p_m \\in \\{1,\\dots,n\\}} \\left( \\frac{1}{n} \\sum_{j=1}^n \\sum_{i=1}^m \\left( x_i + d_i \\cdot |p_i - j| \\right) \\right)\n$$\n\nEquivalently, since the mean is linear:  \n$$\n\\max_{p_1, \\dots, p_m \\in \\{1,\\dots,n\\}} \\left( \\sum_{i=1}^m x_i + \\frac{1}{n} \\sum_{i=1}^m d_i \\sum_{j=1}^n |p_i - j| \\right)\n$$\n\nFor each change $ i $, define:  \n$$\nf_i(p) = \\sum_{j=1}^n |p - j|, \\quad p \\in \\{1, \\dots, n\\}\n$$  \nThen the objective becomes:  \n$$\n\\sum_{i=1}^m x_i + \\sum_{i=1}^m d_i \\cdot \\max_{p \\in \\{1,\\dots,n\\}} f_i(p)\n$$  \n(Note: if $ d_i \\ge 0 $, choose $ p_i $ to maximize $ f_i(p) $; if $ d_i < 0 $, choose $ p_i $ to minimize $ f_i(p) $.)\n\nThus, define for each $ i $:  \n$$\n\\Delta_i = \n\\begin{cases}\n\\max_{p \\in \\{1,\\dots,n\\}} f_i(p) & \\text{if } d_i \\ge 0 \\\\\n\\min_{p \\in \\{1,\\dots,n\\}} f_i(p) & \\text{if } d_i < 0\n\\end{cases}\n$$\n\nThen the maximal arithmetic mean is:  \n$$\n\\frac{1}{n} \\left( \\sum_{i=1}^m x_i + \\sum_{i=1}^m d_i \\cdot \\Delta_i \\right)\n$$\n\n**Final Objective**  \nCompute:  \n$$\n\\boxed{ \\frac{1}{n} \\left( \\sum_{i=1}^m x_i + \\sum_{i=1}^m d_i \\cdot \\Delta_i \\right) }\n$$  \nwhere $ \\Delta_i = \\begin{cases} \\max_p \\sum_{j=1}^n |p - j| & d_i \\ge 0 \\\\ \\min_p \\sum_{j=1}^n |p - j| & d_i < 0 \\end{cases} $, and $ p \\in \\{1, \\dots, n\\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1009C","tags":["greedy","math"],"sample_group":[["2 3\n-1 3\n0 0\n-1 -4","\\-2.500000000000000"],["3 2\n0 2\n5 0","7.000000000000000"]],"created_at":"2026-03-03 11:00:39"}}