{"problem":{"name":"[EGOI 2021] Shopping Fever / 购物热","description":{"content":"海蒂在一个大商店中。她希望购买 $n$ 个商品。 今天是她的幸运日。商店正在进行促销活动：对于每笔账单，顾客获得以下两种优惠之一： 1. 如果买了至少 $3$ 件商品，最便宜的一个免费。 2. 如果买了少于 $3$ 件商品，这笔账单获得 $q\\%$ 的折扣。 海蒂希望不重复地买所有 $n$ 件商品。她可以分成任意笔账单购买。对于每笔账单，将会按照对应的优惠政策打折。 她买所有 $n$ 件商","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9313"},"statements":[{"statement_type":"Markdown","content":"海蒂在一个大商店中。她希望购买 $n$ 个商品。\n\n今天是她的幸运日。商店正在进行促销活动：对于每笔账单，顾客获得以下两种优惠之一：\n\n1. 如果买了至少 $3$ 件商品，最便宜的一个免费。\n2. 如果买了少于 $3$ 件商品，这笔账单获得 $q\\%$ 的折扣。\n\n海蒂希望不重复地买所有 $n$ 件商品。她可以分成任意笔账单购买。对于每笔账单，将会按照对应的优惠政策打折。\n\n她买所有 $n$ 件商品至少需要多少钱？\n\n## Input\n\n第一行两个整数 $n,q$——商品数和买少于 $3$ 件时的折扣比例。\n\n第二行 $n$ 个整数 $p_i$——商品的价格。\n\n另外，保证商品价格可以被 $100$ 整除。因此，每笔账单折扣的价格永远为整数。\n\n## Output\n\n一行，一个整数——至少需要的钱数。\n\n[samples]\n\n## Background\n\nDay 2 Problem A.\n\n题面译自 [EGOI2021 shoppingfever](https://stats.egoi.org/media/task_description/2021_shoppingfever_en.pdf)。\n\n## Note\n\n**样例 $1$ 解释**\n\n海蒂先购买三个价格为 $200$ 元的商品，花费 $400$ 元（免费获得了一个商品）。再购买三个价格为 $300$ 元的商品，花费 $600$ 元（同样免费获得一个）。最后，她购买剩余的价格为 $100$ 元的商品，获得 $10\\%$ 的折扣。\n\n---\n\n**样例 $2$ 解释**\n\n如果海蒂用一笔账单购买三个商品，她获得 $100$ 元的折扣。然而，如果她分三次购买三个商品，获得的折扣变为 $(1000+500+100)\\cdot\\frac{20}{100}=320$ 元。\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le n\\le 10^5$，$0\\le q\\le 100$，$100\\le p_i\\le 10^5$ 且 $100\\mid p_i$。\n\n- 子任务一（$8$ 分）：$n=3$，$100\\le p_i\\le 10^3$。\n- 子任务二（$18$ 分）：$q=0$。\n- 子任务三（$16$ 分）：$q=40$。\n- 子任务四（$22$ 分）：$100\\le p_i\\le 10^3$。\n- 子任务五（$36$ 分）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9313","tags":["动态规划 DP","2021","O2优化","EGOI（欧洲/女生）"],"sample_group":[["7 10\n300 200 200 300 100 300 200","1090"],["3 20\n1000 500 100","1280"],["4 0\n200 100 300 200","600"]],"created_at":"2026-03-03 11:09:25"}}