a260. H.桌遊 - YUTEH ZeroJudge

內容

2021 網際網路程式設計全國⼤賽國中組網路賽

某天，⼩ Y 在桌上看到了⼩ P 前陣⼦在玩的桌遊。這個桌遊有⼀個很⻑的盤⾯，以及⼀些⼩塊的⽅塊，⽤來放上這個盤⾯。每⼀個⽅塊上⾯會寫著⼀個符號以及⼀個數字，符號是加號 + 或是乘號 * 的其中⼀個，⽽數字是介於 1 到 109 的整數。例如，⼀個⽅塊可能是 +87 或者是 *7122。所謂很⻑的盤⾯，指的是可以依序將每個⽅塊放上這個盤⾯。這個盤⾯恰巧可以放上所有的⽅塊，⽽為了結束這個遊戲，玩家也必須將所有的⽅塊放上這個盤⾯。當放完所有⽅塊之後就是計分環節。⾸先，玩家⼀開始的分數是 0 分。接下來，按照玩家放上⽅塊的順序，去改動玩家的分數。例如，對於 +3，+5，*7 這三個⽅塊，如果玩家放上的⽅塊的順序是 +3，*7，+5，那麼玩家最後的分數就會是 (((0 + 3) ∗ 7) + 5) = 26；但如果玩家放上⽅塊的順序是 +5，*7，+3，那麼玩家最後的分數就會是 (((0 + 5) ∗ 7) + 3) = 38。現在，知道了這個遊戲內容的⼩ Y 不禁覺得這樣的遊戲好像太無聊了點。於是，他決定把每個⽅塊加上⼀個限制：對於第 i 個⽅塊，只有在盤⾯上的⽅塊不少於 ci 個的時候才能放上盤⾯。⼩ Y 不禁開始思考，在這樣⼦的條件之下，最⾼可以獲得的得分是多少？

輸入說明

輸⼊的第⼀⾏是⼀個正整數 N，代表⽅塊的總數。接下來的 N ⾏，第 i ⾏會有⼀個字串 si 跟⼀個數字 ci。si 是由兩個部份所構成：第⼀個字元會是 + 或 * 的其中⼀個，然後後⾯接著⼀個正整數 xi。這代表第 i 個⽅塊上⾯寫的字，以及放上這個⽅塊之前，版⾯上最少要有多少個⽅塊。 • 1 ≤ N ≤ 2 × 105 • 1 ≤ xi ≤ 109 • 0 ≤ ci ≤ N − 1

輸出說明

如果在這樣的條件下無法放上所有的⽅塊，請輸出 -1。否則，請輸出最⾼可以獲得的分數。因為這個分數可能會很⼤，所以請輸出這個分數除以 109 + 7 的餘數。請注意，要輸出的數字是最⾼的分數除以 109 + 7 之後的餘數，並不是分數除以 109 + 7 之後餘數的最⾼數值。舉例來說，如果最⾼分的策略可以得到 109 + 8 分，且有另⼀種可以得到 109 + 6 的策略，雖然 109 + 8 除以 109 + 7 後的餘數為 1，你仍然應該輸出 1 ⽽不是 109 + 6。

範例輸入

範例輸出

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (0%): 1.0s , <10M
公開測資點#1 (0%): 1.0s , <1K
公開測資點#2 (0%): 1.0s , <1K
公開測資點#3 (0%): 1.0s , <1K
公開測資點#4 (0%): 1.0s , <1K
公開測資點#5 (0%): 1.0s , <1K
公開測資點#6 (0%): 1.0s , <1K
公開測資點#7 (0%): 1.0s , <1K
公開測資點#8 (0%): 1.0s , <1K
公開測資點#9 (0%): 1.0s , <1K
公開測資點#10 (0%): 1.0s , <1K
公開測資點#11 (0%): 1.0s , <1K
公開測資點#12 (0%): 1.0s , <1K
公開測資點#13 (0%): 1.0s , <1K
公開測資點#14 (0%): 1.0s , <1K
公開測資點#15 (0%): 1.0s , <1K
公開測資點#16 (0%): 1.0s , <1K
公開測資點#17 (0%): 1.0s , <1K
公開測資點#18 (0%): 1.0s , <1K
公開測資點#19 (0%): 1.0s , <1K
公開測資點#20 (0%): 1.0s , <1K
公開測資點#21 (0%): 1.0s , <1K
公開測資點#22 (0%): 1.0s , <1K
公開測資點#23 (0%): 1.0s , <1K
公開測資點#24 (0%): 1.0s , <1K
公開測資點#25 (0%): 1.0s , <1K
公開測資點#26 (0%): 1.0s , <1K
公開測資點#27 (0%): 1.0s , <1K
公開測資點#28 (0%): 1.0s , <1K
公開測資點#29 (0%): 1.0s , <1K
公開測資點#30 (0%): 1.0s , <1K
公開測資點#31 (0%): 1.0s , <1K
公開測資點#32 (0%): 1.0s , <1K
公開測資點#33 (0%): 1.0s , <1K
公開測資點#34 (0%): 1.0s , <1K
公開測資點#35 (0%): 1.0s , <1K
公開測資點#36 (0%): 1.0s , <1K
公開測資點#37 (0%): 1.0s , <1K
公開測資點#38 (0%): 1.0s , <1K
公開測資點#39 (0%): 1.0s , <1K
公開測資點#40 (0%): 1.0s , <1K
公開測資點#41 (0%): 1.0s , <1M
公開測資點#42 (0%): 1.0s , <1M
公開測資點#43 (0%): 1.0s , <1M
公開測資點#44 (0%): 1.0s , <1M
公開測資點#45 (0%): 1.0s , <1M
公開測資點#46 (0%): 1.0s , <1M
公開測資點#47 (0%): 1.0s , <1M
公開測資點#48 (0%): 1.0s , <1M
公開測資點#49 (0%): 1.0s , <1M
公開測資點#50 (0%): 1.0s , <1M
公開測資點#51 (0%): 1.0s , <1M
公開測資點#52 (0%): 1.0s , <1M
公開測資點#53 (0%): 1.0s , <1M
公開測資點#54 (0%): 1.0s , <1M
公開測資點#55 (0%): 1.0s , <1M
公開測資點#56 (0%): 1.0s , <1M
公開測資點#57 (0%): 1.0s , <1M
公開測資點#58 (0%): 1.0s , <1M
公開測資點#59 (0%): 1.0s , <1M
公開測資點#60 (0%): 1.0s , <1M
公開測資點#61 (0%): 1.0s , <10M
公開測資點#62 (0%): 1.0s , <10M
公開測資點#63 (0%): 1.0s , <10M
公開測資點#64 (0%): 1.0s , <10M
公開測資點#65 (0%): 1.0s , <10M
公開測資點#66 (0%): 1.0s , <10M
公開測資點#67 (0%): 1.0s , <10M
公開測資點#68 (0%): 1.0s , <10M
公開測資點#69 (0%): 1.0s , <10M
公開測資點#70 (0%): 1.0s , <10M
公開測資點#71 (0%): 1.0s , <10M
公開測資點#72 (0%): 1.0s , <10M
公開測資點#73 (0%): 1.0s , <10M
公開測資點#74 (0%): 1.0s , <10M
公開測資點#75 (0%): 1.0s , <10M
公開測資點#76 (0%): 1.0s , <10M
公開測資點#77 (0%): 1.0s , <10M
公開測資點#78 (0%): 1.0s , <10M
公開測資點#79 (0%): 1.0s , <10M
公開測資點#80 (0%): 1.0s , <10M
公開測資點#81 (0%): 1.0s , <10M
公開測資點#82 (0%): 1.0s , <10M
公開測資點#83 (0%): 1.0s , <10M
公開測資點#84 (0%): 1.0s , <10M
公開測資點#85 (0%): 1.0s , <10M
公開測資點#86 (0%): 1.0s , <10M
公開測資點#87 (0%): 1.0s , <10M
公開測資點#88 (0%): 1.0s , <10M
公開測資點#89 (0%): 1.0s , <10M
公開測資點#90 (1%): 1.0s , <10M
公開測資點#91 (1%): 1.0s , <10M
公開測資點#92 (1%): 1.0s , <10M
公開測資點#93 (1%): 1.0s , <10M
公開測資點#94 (1%): 1.0s , <10M
公開測資點#95 (1%): 1.0s , <10M
公開測資點#96 (1%): 1.0s , <10M
公開測資點#97 (1%): 1.0s , <10M
公開測資點#98 (1%): 1.0s , <10M
公開測資點#99 (1%): 1.0s , <10M
公開測資點#100 (1%): 1.0s , <10M
公開測資點#101 (1%): 1.0s , <10M
公開測資點#102 (1%): 1.0s , <10M
公開測資點#103 (1%): 1.0s , <10M
公開測資點#104 (1%): 1.0s , <10M
公開測資點#105 (1%): 1.0s , <10M
公開測資點#106 (1%): 1.0s , <10M
公開測資點#107 (1%): 1.0s , <10M
公開測資點#108 (1%): 1.0s , <10M
公開測資點#109 (1%): 1.0s , <10M
公開測資點#110 (1%): 1.0s , <10M
公開測資點#111 (1%): 1.0s , <10M
公開測資點#112 (1%): 1.0s , <10M
公開測資點#113 (1%): 1.0s , <10M
公開測資點#114 (1%): 1.0s , <10M
公開測資點#115 (1%): 1.0s , <10M
公開測資點#116 (1%): 1.0s , <10M
公開測資點#117 (1%): 1.0s , <10M
公開測資點#118 (1%): 1.0s , <10M
公開測資點#119 (1%): 1.0s , <10M
公開測資點#120 (1%): 1.0s , <10M
公開測資點#121 (1%): 1.0s , <10M
公開測資點#122 (1%): 1.0s , <10M
公開測資點#123 (1%): 1.0s , <10M
公開測資點#124 (1%): 1.0s , <10M
公開測資點#125 (1%): 1.0s , <10M
公開測資點#126 (1%): 1.0s , <10M
公開測資點#127 (1%): 1.0s , <10M
公開測資點#128 (1%): 1.0s , <10M
公開測資點#129 (1%): 1.0s , <10M
公開測資點#130 (1%): 1.0s , <10M
公開測資點#131 (1%): 1.0s , <10M
公開測資點#132 (1%): 1.0s , <10M
公開測資點#133 (1%): 1.0s , <10M
公開測資點#134 (1%): 1.0s , <10M
公開測資點#135 (1%): 1.0s , <10M
公開測資點#136 (1%): 1.0s , <10M
公開測資點#137 (1%): 1.0s , <10M
公開測資點#138 (1%): 1.0s , <10M
公開測資點#139 (1%): 1.0s , <10M
公開測資點#140 (1%): 1.0s , <10M
公開測資點#141 (1%): 1.0s , <10M
公開測資點#142 (1%): 1.0s , <10M
公開測資點#143 (1%): 1.0s , <10M
公開測資點#144 (1%): 1.0s , <10M
公開測資點#145 (1%): 1.0s , <10M
公開測資點#146 (1%): 1.0s , <10M
公開測資點#147 (1%): 1.0s , <10M
公開測資點#148 (1%): 1.0s , <10M
公開測資點#149 (1%): 1.0s , <10M
公開測資點#150 (1%): 1.0s , <10M
公開測資點#151 (1%): 1.0s , <10M
公開測資點#152 (1%): 1.0s , <10M
公開測資點#153 (1%): 1.0s , <10M
公開測資點#154 (1%): 1.0s , <10M
公開測資點#155 (1%): 1.0s , <10M
公開測資點#156 (1%): 1.0s , <10M
公開測資點#157 (1%): 1.0s , <10M
公開測資點#158 (1%): 1.0s , <10M
公開測資點#159 (1%): 1.0s , <10M
公開測資點#160 (1%): 1.0s , <10M
公開測資點#161 (1%): 1.0s , <10M
公開測資點#162 (1%): 1.0s , <10M
公開測資點#163 (1%): 1.0s , <10M
公開測資點#164 (1%): 1.0s , <10M
公開測資點#165 (1%): 1.0s , <10M
公開測資點#166 (1%): 1.0s , <10M
公開測資點#167 (1%): 1.0s , <10M
公開測資點#168 (1%): 1.0s , <10M
公開測資點#169 (1%): 1.0s , <10M
公開測資點#170 (1%): 1.0s , <10M
公開測資點#171 (1%): 1.0s , <10M
公開測資點#172 (1%): 1.0s , <10M
公開測資點#173 (1%): 1.0s , <10M
公開測資點#174 (1%): 1.0s , <10M
公開測資點#175 (1%): 1.0s , <10M
公開測資點#176 (1%): 1.0s , <10M
公開測資點#177 (1%): 1.0s , <10M
公開測資點#178 (1%): 1.0s , <10M
公開測資點#179 (1%): 1.0s , <10M
公開測資點#180 (1%): 1.0s , <10M
公開測資點#181 (1%): 1.0s , <10M
公開測資點#182 (1%): 1.0s , <10M
公開測資點#183 (1%): 1.0s , <10M
公開測資點#184 (1%): 1.0s , <10M
公開測資點#185 (1%): 1.0s , <10M
公開測資點#186 (1%): 1.0s , <10M
公開測資點#187 (1%): 1.0s , <10M
公開測資點#188 (1%): 1.0s , <10M
公開測資點#189 (1%): 1.0s , <10M

提示：

標籤:

2021國中組網路賽

出處:

NPSC [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」