TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2434
  • 题目
  • P2434果园看守
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    重庆有很多区县都盛产水果,每当到了水果成熟的时节,何老板就会看准商机,推出了一项名为“果园守望者”的服务。该服务很简单,就是何老板安排人手去为你看守果园,帮你驱赶鸟兽或者小偷。
    最近,何老板又签下了一个看守合同,该合同需要何老板派人看守一个果园,时间是从第A天起一直到第B天。在这B-A+1天里,要求每天至少有一个人在看守果园。
    何老板手下共有N个员工。每个员工都对自己的工作时间和报酬有一定的要求,比如员工甲只在T1..T2这段时间工作,并要求S1元的报酬;员工乙只在T3..T4这段时间工作,并要求S2元的报酬......
    请你帮助何老板安排一个工作时间表,使得从第A天到第B天每天至少有一个员工在看守果园,并且使得何老板支付的报酬总数尽可能少。

    输入格式

    第一行,三个空格间隔的整数N,A,B
    接下来N行,每行三个整数T1,T2,和S,表示对应员工愿意工作的起止时间和要求的报酬。

    输出格式

    一个整数,表示何老板需支付的最少报酬总数。如果无法安排员工完成工作,输出-1

    样例输入 1

    3 0 4
    0 2 3
    3 4 2
    0 0 1

    样例输出 1

    5

    样例输入 2

    5 0 4
    2 2 2
    1 1 1
    4 4 4
    0 0 0
    3 3 3

    样例输出 2

    10

    提示

    1 <= N <= 10,000
    0 <= A <= B <= 90000
    A <= T1 <= T2 <= B
    0 <= S <= 500,000
    样例1说明
    安排第一个员工工作0,1,2三天
    安排第二个员工工作3,4两天
    就把从第0天到第4天这5天的看守工作完成了。