{"problem":{"name":"C. Ремонт забора","description":{"content":"Забор состоит из $N$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFC"},"statements":[{"statement_type":"Markdown","content":"Забор состоит из $N$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают $L$ разных видов: шириной в 1 доску, в 2 доски, ... , в $L$ досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более $L$ подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.   Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какие наименьшее число щитов необходимо приобрести, чтобы починить весь забор.\n\nПервая строка входных данных содержит целое число $L$ ($L > 0$) — максимальный размер щита. Во второй строке входных данных записано целое число $N$ ($N > 0$) — количество досок в заборе. Следующие $N$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.\n\nПрограмма должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.\n\nРешение, правильно работающее только для случаем когда числа $L$ и $N$ не превосходят 1000, будет оцениваться в 60 баллов.\n\n В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $10^5$.\n\nМаксимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.\n\n## Входные Данные\n\nПервая строка входных данных содержит целое число $L$ ($L > 0$) — максимальный размер щита. Во второй строке входных данных записано целое число $N$ ($N > 0$) — количество досок в заборе. Следующие $N$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.\n\n## Выходные Данные\n\nПрограмма должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.\n\n## Пример\n\nВходные данные3\n8\n0\n0\n1\n0\n1\n0\n1\n0\nВыходные данные2\n\n## Примечание\n\nМаксимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.\n\n## Система Оценки\n\nРешение, правильно работающее только для случаем когда числа $L$ и $N$ не превосходят 1000, будет оцениваться в 60 баллов. В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $10^5$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Tom 最近喜欢玩一款电子游戏。该游戏的规则如下：游戏在一条 $x$-轴上进行。游戏中共有 $n + 1$ 个柱子，从左到右排成一行，柱子编号为 $0$ 到 $n$，编号为 $i$ 的柱子坐标为 $x = i$。此外，游戏中还有一个无限延伸的平台，覆盖范围为 $[ n + 1, + \\infty)$。玩家只要跳到该范围内的任意位置即可 *获胜*。\n\n玩家从编号为 $0$ 的柱子出发，只能向右跳跃（即坐标必须递增），且只能落在柱子或平台上，否则会掉入虚空而 *失败*。此外，玩家的跳跃能力有限，每次跳跃的距离不超过 $p$。\n\n除了编号为 $0$ 的柱子外，其余每个柱子上都有一宝箱。编号为 $i$ 的柱子上的宝箱包含 $a_i$ 枚金币。但有些是陷阱宝箱（$a_i < 0$），玩家会失去 $| a_i |$ 枚金币。\n\n该游戏共有 $n$ 个关卡。在第 $i$ 个关卡中，Tom 只能跳到编号为 $i$ 的倍数的柱子上。现在有 $q$ 个查询，每个查询给出一个数 $x$，要求计算 Tom 在第 $x$ 个关卡中 *获胜* 时能获得的最大金币数。可能 Tom 在途中打开了太多陷阱宝箱，导致最终金币数为负。\n\n第一行包含三个整数 $n$、$q$ 和 $p$（$2 \\leq p \\leq n \\leq 10^6$，$1 \\leq q \\leq 10^6$），分别表示柱子数量、查询数量和最大跳跃距离。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$| a_i | \\leq 10^9$），表示编号为 $i$ 的柱子上宝箱的金币数量。\n\n接下来 $q$ 行，每行包含一个整数 $x$（$1 \\leq x \\leq n$），表示一个查询，要求计算在第 $x$ 个关卡中能获得的最大金币数。\n\n对每个查询，输出一行一个整数表示答案。如果无法获胜，请输出 _Noob_。\n\n## Input\n\n第一行包含三个整数 $n$、$q$ 和 $p$（$2 \\leq p \\leq n \\leq 10^6$，$1 \\leq q \\leq 10^6$），表示柱子数量、查询数量和最大跳跃距离。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$| a_i | \\leq 10^9$），表示编号为 $i$ 的柱子上宝箱的金币数量。接下来 $q$ 行，每行包含一个整数 $x$（$1 \\leq x \\leq n$），表示一个查询，要求计算在第 $x$ 个关卡中能获得的最大金币数。\n\n## Output\n\n对每个查询，输出一行一个整数表示答案。如果无法获胜，请输出 _Noob_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q, p \\in \\mathbb{Z} $ with $ 2 \\leq p \\leq n \\leq 10^6 $, $ 1 \\leq q \\leq 10^6 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $, where $ a_i $ is the gold coin value at pillar $ i $.  \nLet $ \\mathcal{P} = \\{0, 1, 2, \\dots, n\\} $ be the set of pillar positions.  \nLet $ \\mathcal{F} = [n+1, +\\infty) $ be the winning platform.  \n\n**Constraints**  \n1. Player starts at pillar $ 0 $.  \n2. Player may only jump rightward (increasing $ x $-coordinate).  \n3. Each jump has length $ \\leq p $.  \n4. In level $ x $, player may only land on pillars at positions $ i $ where $ x \\mid i $, or the platform.  \n5. Player wins by reaching any position in $ \\mathcal{F} $.  \n\n**Objective**  \nFor each query $ x \\in \\{1, \\dots, n\\} $, compute the maximum total gold coins collectible along a valid path from pillar $ 0 $ to $ \\mathcal{F} $, where allowed landing positions are $ \\{0\\} \\cup \\{ i \\in \\{1, \\dots, n\\} \\mid x \\mid i \\} \\cup \\mathcal{F} $, and each jump $ \\leq p $.  \n\nIf no such path exists, output `Noob`.  \nOtherwise, output:  \n$$\n\\max \\left\\{ \\sum_{\\substack{i \\in \\{1,\\dots,n\\} \\\\ x \\mid i \\\\ \\text{visited}}} a_i \\,\\middle|\\, \\text{valid path from } 0 \\text{ to } \\mathcal{F} \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFC","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}