• [1304] BJF: How Far Can Drive At Most

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Now I am going to drive on a street. The street is a straight line. It will cost me one unit oil per meter. And my car can contain V units at most. Unfortunately some zones of the street have been damaged badly. The number of damaged zones is Q. One zone is represented as (l, r, C), means the zone between l to r is damaged, and it will cost me another C units of oil per peter. Please notice that zones may intersect. My question is how far can I drive at most.


  • 输入
  • Several cases(cases <= 10). The first line is the case number T. Then T cases follow. For each case : First line two integers l (indicating the length of the street) and V (indicating the amount of oil my car can contain at most when I start)(1 <= len, V <= 10 ^ 9). Second line of each case is an integer Q (0 <= Q <= 50000). Then Q lines follow, each with three integers (l, r, C), means the zone between l to r has been damaged and it will cost me another C units of oil per meter(1 <= l < r <= len, 1 <= C <= 100).
  • 输出
  • For each case, print the farthest I can drive, and output it with exactly two digits after the decimal point.
  • 样例输入
  • 2
    100 100
    2
    10 20 5
    10 30 14
    1000 10000
    3
    10 20 4
    10 30 14
    10 15 5
  • 样例输出
  • 14.50
    1000.00
  • 提示
  • 来源
  • 加多宝凉茶
  • 操作

显示春菜