[蓝桥杯 2022 国 C] 打折

Luogu
IDLGP8812
Time1000ms
Memory128MB
DifficultyP4
2022枚举差分蓝桥杯国赛
小蓝打算采购 $n$ 种物品,每种物品各需要 $1$ 个。 小蓝所住的位置附近一共有 $m$ 个店铺,每个店铺都出售着各种各样的物品。 第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折,折扣率为 $p_i$,对于原件为 $b$ 的物品,折后价格为 $\lfloor\frac {b\cdot p_j}{100}\rfloor$。其它时间需按原价购买。 小蓝很忙,他只能选择一天的时间去采购这些物品。请问,他最少需要花多少钱才能买到需要的所有物品。 题目保证小蓝一定能买到需要的所有物品。 ## Input 输入的第一行包含两个整数 $n,m$,用一个空格分隔,分别表示物品的个数和店铺的个数。 接下来依次包含每个店铺的描述。每个店铺由若干行组成,其中第一行包含四个整数 $s_i,t_i, p_i,c_i$,相邻两个整数之间用一个空格分隔,分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 $c_i$ 行,每行包含两个整数 $a_j,b_j$,用一个空格分隔,分别表示该商店的第 $j$ 个商品的类型和价格。商品的类型由 $1$ 至 $n$ 编号。 ## Output 输出一行包含一个整数表示小蓝需要花费的最少的钱数。 [samples] ## Note 对于 $40\%$ 的评测用例,$n,m≤500,s_i ≤t_i ≤100,\sum c_i ≤2000$; 对于 $70\%$ 的评测用例,$n,m≤5000,\sum c_i ≤20000$; 对于所有评测用例,$1 ≤ n,m ≤ 10^5,1 ≤ c_i ≤ n,\sum c_i ≤ 4\times10^5,1 ≤ s_i ≤t_i ≤10^9,1 < p_i < 100,1≤a_j ≤n,1≤b_j ≤10^9$。 蓝桥杯 2022 国赛 C 组 I 题。
Samples
Input #1
2 2
1 2 89 1
1 97
3 4 77 1
2 15
Output #1
101
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2022 国 C] 打折",
    "description": {
      "content": "小蓝打算采购 $n$ 种物品,每种物品各需要 $1$ 个。 小蓝所住的位置附近一共有 $m$ 个店铺,每个店铺都出售着各种各样的物品。 第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折,折扣率为 $p_i$,对于原件为 $b$ 的物品,折后价格为 $\\lfloor\\frac {b\\cdot p_j}{100}\\rfloor$。其它时间需按原价购买。 小蓝很忙,他只能选择一天的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8812"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝打算采购 $n$ 种物品,每种物品各需要 $1$ 个。\n\n小蓝所住的位置附近一共有 $m$ 个店铺,每个店铺都出售着各种各样的物品。\n\n第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折,折扣率为 $p_i$,对于原件为 $b$ 的物品,折后价格为 $\\lfloor\\frac {b\\cdot p_j}{100}\\rfloor$。其它时间需按原价购买。\n\n小蓝很忙,他只能选择一天的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments