首页分享 P8812 [蓝桥杯 2022 国 C] 打折

P8812 [蓝桥杯 2022 国 C] 打折

来源：花匠小妙招时间：2024-11-14 14:04

洛谷推荐

题目描述

小蓝打算采购 nn 种物品，每种物品各需要 11 个。

小蓝所住的位置附近一共有 mm 个店铺，每个店铺都出售着各种各样的物品。

第 ii 家店铺会在第 sis_i 天至第 tit_i 天打折，折扣率为 pip_i，对于原件为 bb 的物品，折后价格为 ⌊b⋅pj100⌋lfloorfrac {bcdot p_j}{100}rfloor。其它时间需按原价购买。

小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。

题目保证小蓝一定能买到需要的所有物品。

输入格式

输入的第一行包含两个整数 n,mn,m，用一个空格分隔，分别表示物品的个数和店铺的个数。

接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 si,ti,pi,cis_i,t_i, p_i,c_i，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 cic_i 行，每行包含两个整数 aj,bja_j,b_j，用一个空格分隔，分别表示该商店的第 jj 个商品的类型和价格。商品的类型由 11 至 nn 编号。

输出格式

输出一行包含一个整数表示小蓝需要花费的最少的钱数。

输入输出样例

输入 #1

2 2 1 2 89 1 1 97 3 4 77 1 2 15

说明/提示

对于 40%40% 的评测用例，n,m≤500，si≤ti≤100，∑ci≤2000n,m≤500，s_i ≤t_i ≤100，sum c_i ≤2000；

对于 70%70% 的评测用例，n,m≤5000，∑ci≤20000n,m≤5000，sum c_i ≤20000；

对于所有评测用例，1≤n,m≤105，1≤ci≤n，∑ci≤4×105，1≤si≤ti≤109，1<pi<100，1≤aj≤n，1≤bj≤1091 ≤ n,m ≤ 10^5，1 ≤ c_i ≤ n，sum c_i ≤ 4times10^5，1 ≤ s_i ≤t_i ≤10^9，1 < p_i < 100，1≤a_j ≤n，1≤b_j ≤10^9。

蓝桥杯 2022 国赛 C 组 I 题。

原文链接: P8812 [蓝桥杯 2022 国 C] 打折 https://www.huajiangbk.com/newsview546947.html

分类：花卉