TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5914
  • 問題
  • P5914【崛起的欢乐赛】白蛇缘起
    制限 : 時間制限 : - MS   メモリ制限 : 262144 KB
    問題説明

    她清丽高雅,仙灵柔美,性格坚韧独立、坚贞不渝,在修炼遇劫不得突破时,由此解开了五百年前一段人妖相恋的尘封记忆。

    白蛇的这段记忆是被法术封印的。共有$n$道独立的法术封印,第$i$道法术封印的强度为$a_i$。法术封印的强度会随着时间流逝而衰减,第$i$道法术封印的强度每过$b_i$天会减少$c_i$。法术封印的衰减是瞬发的,第$i$道封印的强度在第$0$到都$b_i-1$天都是$a_i$,在第$b_i$天到第$2b_i-1$天都是$a_i-c_i$,在第$2b_i$到第$3b_i-1$天都是$a_i-2c_i$,以此类推,直到衰减到$0$为止。封印强度衰减到$0$表示这道封印自动解除了。

    白蛇和青蛇都在努力的解除这些封印。白蛇可以解除至多$p$道封印,青蛇可以解除强度总和不超过$q$的若干道封印。但是,这样的操作白蛇和青蛇至多各施展一次,那么,白蛇至少需要等待多少天,才能解除所有封印?

    入力形式

    第一行三个整数$n,p,q$,表示封印总条数、白蛇能够解除的封印条数、青蛇能够解除的封印强度总和上限。

    接下来$n$行,每行三个整数$a_i,b_i,c_i$,表示第$i$条封印的初始强度和衰减规律。

    出力形式

    输出一行,一个整数,表示至少要等待到哪天,才能解除所有的封印。

    サンプル入力 1

    5 1 3
    100 100 1
    10 1 1
    10 2 5
    10 3 5
    2 6 6 

    サンプル出力 1

    7

    サンプル入力 2

    1 0 0
    1000000000 1000000000 1

    サンプル出力 2

    1000000000000000000

    サンプル入力 3

    2 1 1
    1000000000 1000000000 1
    100000000 343896 12687523

    サンプル出力 3

    2751168

    ヒント

    样例说明1

    共有$5$条封印,白蛇可以解除$1$条封印,青蛇可以解除强度总和不超过$3$的若干条封印。在第$7$天,每条封印的剩余强度分别为$100,3,0,0,0$。此时白蛇解除第$1$道封印,青蛇解除第$2$道封印,则所有封印都被解除。

    样例说明2

    白蛇和青蛇都不能进行任何操作,只能等待封印自动解除。

    数据规模与约定

    对于30%的数据,\(n\le500\)
    对于另外30%的数据,所有的封印都会在$500$天内自动衰减到$0$;
    对于100%的数据,$1\le n\le 50000,\ 0\le p\le n,\ 0\le q\le 10^{9}$,其他数据都是正整数且不超过$10^9$。


    ソース  感谢nodgd命题