Dotcpp  /  编程题库  /  蓝桥杯2022年第十三届决赛真题-打折（Python组）
题目 2730:

蓝桥杯2022年第十三届决赛真题-打折（Python组）

 时间限制: 2s 内存限制: 256MB

题目描述

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

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

第 i 家店铺会在第 si 天至第 ti 天打折，折扣率为 pi，对于原件为 b 的物品，折后价格为蓝桥杯2022年第十三届决赛真题-打折（Python组）  。其它时间需按原价购买。

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

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

输入格式

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

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

输出格式

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

样例输入

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

样例输出

101

提示

对于 40% 的评测用例，n, m ≤ 500 ，si ≤ ti ≤ 100 ，∑ ci ≤ 200000 ；

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

对于所有评测用例，1 ≤ n, m ≤ 100000，1≤ ci≤ n ， ∑ ci ≤ 400000 ，1 ≤ si ≤ ti ≤ 109 ，1 < pi < 100 ，1 ≤ aj ≤ n ，1 ≤ bj ≤ 109 。

本试题适用于用Python代码来完成，如用c/c++/java代码建议转到：https://www.dotcpp.com/oj/problem2707.html链接

标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
蓝桥杯2022年第十三届决赛真题-卡牌
蓝桥杯2016年第七届真题-四平方和
蓝桥杯2016年第七届真题-压缩变换
蓝桥杯2016年第七届真题-最大比例
蓝桥杯2018年第九届真题-航班时间