TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5960
  • 题目
  • P5960「ROI 2017 Day 2」学习轨迹
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2S,512M
    问题描述

    译自 ROI 2017 Day 2 T4. Траектория обучения

    T 大和 P 大同时向一位神犇抛出了橄榄枝。
    清华有 \(n\) 门课程,课程的编号分别为 \(a_1\dots a_n\)(注意不是 $1\ldots n$),\(i\) 号课程的质量为 \(x_i\)。北大有 \(m\) 门课程,课程的编号分别为 \(b_1\dots b_m\)\(i\) 号课程的质量为 \(y_i\)。清华和北大开设的课程可能相同(即编号相同)。
    神犇可以在清华学习课程 \(l_a\sim r_a\) \((1⩽ l_a⩽ r_a⩽ n)\),也可以不去清华。同时,神犇可以在北大学习课程 \(l_b\sim r_b\) \((1⩽ l_b⩽ r_b⩽ n)\),也可以不去北大。神犇太强了,他可以两所学校都去。
    神犇不想把时间浪费在同样的课程上。因此,神犇不会选择两门相同的课程。
    试求:神犇能听到的课程的质量总和的最大值 \(r\)

    输入格式

    第一行:\(n,m\)
    第二行:\(a_1\dots a_n\)
    第三行:\(x_1\dots x_n\)
    第四行:\(b_1\dots b_n\)
    第五行:\(y_1\dots y_n\)

    输出格式

    第一行:\(r\)
    第二行:\(l_a, r_a\)(如果神犇不打算在清华听课,请输出 0 0)。
    第三行:\(l_b, r_b\)(如果神犇不打算在北大听课,请输出 0 0)。

    提示

    样例输入 1

    7 5
    3 1 4 8 6 9 2
    2 7 4 10 1 5 3
    9 2 11 3 8
    3 5 3 4 12
    

    样例输出 1

    39
    2 6
    2 4
    

    样例说明 1

    最优解如样例所示,课程质量之和为 \((7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39.\)
    次优解:\((7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38.\)

    样例输入 2

    2 3
    1 2
    1 4
    2 3 1
    17 2 15
    

    样例输出 2

    34
    0 0
    1 3
    

    样例说明 2

    由于北大的 $1$ 号、$2$ 号课程相比清华的相同课程的质量要高得多,因此最优解是拒掉清华,转而在北大读 $1\sim 3$ 号课程。

    样例输入 3

    3 3
    4 2 1
    10 1 2
    5 4 2
    1 2 9
    

    样例输出 3

    19
    1 1
    3 3
    

    对于所有数据,$1 ⩽ n, m ⩽ 5\times 10^5.$

    子任务编号 分值 \(n,m ⩽\) 子任务编号 分值 \(n,m ⩽\)
    1 10 $50$ 6 5 $5000$
    2  10  $100$ 7  5  $10^4$
    3 10 $300$ 8  10  $3\times 10^4$
    4  10  $500$ 9 10 $10^5$
    5 10 $2000$ 10  10  $2.5\times 10^5$
      11 10 $5\times 10^5$

    点此提交