題目 2730:
藍(lán)橋杯2022年第十三屆決賽真題-打折（Python組）
時(shí)間限制: 5s
內(nèi)存限制: 512MB 提交: 140 解決: 19
題目描述
小藍(lán)打算采購(gòu) n 種物品，每種物品各需要 1 個(gè)。
小藍(lán)所住的位置附近一共有 m 個(gè)店鋪，每個(gè)店鋪都出售著各種各樣的物品。
第 i 家店鋪會(huì)在第 si 天至第 ti 天打折，折扣率為 pi，對(duì)于原件為 b 的物品，折后價(jià)格為
。其它時(shí)間需按原價(jià)購(gòu)買。
。其它時(shí)間需按原價(jià)購(gòu)買。
小藍(lán)很忙，他只能選擇一天的時(shí)間去采購(gòu)這些物品。請(qǐng)問(wèn)，他最少需要花多少錢才能買到需要的所有物品。
題目保證小藍(lán)一定能買到需要的所有物品。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) n, m，用一個(gè)空格分隔，分別表示物品的個(gè)數(shù)和店鋪的個(gè)數(shù)。
接下來(lái)依次包含每個(gè)店鋪的描述。每個(gè)店鋪由若干行組成，其中第一行包含四個(gè)整數(shù) si, ti, pi, ci，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，分別表示商店優(yōu)惠的起始和結(jié)束時(shí)間、折扣率以及商店內(nèi)的商品總數(shù)。之后接 ci 行，每行包含兩個(gè)整數(shù) aj, bj ，用一個(gè)空格分隔，分別表示該商店的第 j 個(gè)商品的類型和價(jià)格。商品的類型由 1 至 n 編號(hào)。
輸出格式
輸出一行包含一個(gè)整數(shù)表示小藍(lán)需要花費(fèi)的最少的錢數(shù)。
樣例輸入
2 2 1 2 89 1 1 97 3 4 77 1 2 15
樣例輸出
101
提示
對(duì)于 40% 的評(píng)測(cè)用例，n, m ≤ 500 ，si ≤ ti ≤ 100 ，∑ ci ≤ 200000 ；
對(duì)于 70% 的評(píng)測(cè)用例，n, m ≤ 5000 ，∑ ci ≤ 200000 ；
對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 100000，1≤ ci≤ n ， ∑ ci ≤ 400000 ，1 ≤ si ≤ ti ≤ 109 ，1 < pi < 100 ，1 ≤ aj ≤ n ，1 ≤ bj ≤ 109 。
本試題適用于用Python代碼來(lái)完成，如用c/c++/java代碼建議轉(zhuǎn)到：http://www.sztianhecheng.cn/oj/problem2707.html鏈接