P2686 老虎的题目

    • 46通过
    • 144提交
  • 题目提供者 zhuowei
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    随着小老虎做题越来越多,现在可做小老师了,小老虎经常帮老师出题供信息学奥赛班的同学测试用。出题确实是一件麻烦事。现在有更麻烦的事了:

    小老虎收集到了一大堆的题目,并且按照收集的时间顺序排成一排。每个题目都有自己的题面长度和难度。小老虎想用这些题出好多好多场比赛。但是呢,有要求:

    同一场比赛的题目,必须是这一排中,连续的一段,但题目数量不限。

    题面长度的总和,不能超过high,也不能低于low。

    不允许出现两场比赛,使得其中一场的题目全部在另一场出现过了。(就是说,不同比赛的题目集合不能出现包含和被包含关系)

    题目可以在不同比赛中重复使用。

    现在,小老虎想知道,在满足以上条件的基础上……对不起,小老虎不是想知道最多出多少场,而是想知道,所有比赛的难度总和最大是多少?(定义一场比赛的难度为本场比赛出现的所有题目的难度和)

    输入输出格式

    输入格式:

    第一行是三个整数,N、low、high。

    第二行有N个整数,描述了题面的长度。

    第三行有N个整数,描述了题目的难度。

    输出格式:

    输出一个整数,所有比赛的最大难度总和。

    输入输出样例

    输入样例#1: 复制
    6 4 5
    1 3 3 2 2 1
    2 3 1 4 5 2
    
    输出样例#1: 复制
    21
    
    注:样例中,3场,第一场选1,2两题,第二场选3,4两题,第三场选4,5,6三题。
    

    说明

    对于40%的数据,1 <= N <= 100;

    对于100%的数据,1 <= N <= 1000;

    单个题目的题面长度和难度都小等于100000;

    其余给出的均在longint范围内。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。