#PQJ388x3263. QOJ 388_3263

    ID: 2937 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:六省联合省选2017

QOJ 388_3263

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试期末考试(exam) 期末考试(exam) 【问题描述】 有n 位同学,每位同学都参加了全部的m 门课程的期末考试,都在焦急的等待成 绩的公布。 第i 位同学希望在第ti 天或之前得知.所.有课程的成绩。如果在第ti 天,有至少一 门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产 生C 不愉快度。 对于第i 门课程,按照原本的计划,会在第bi 天公布成绩。 有如下两种操作可以调整公布成绩的时间:

  1. 将负责课程X 的部分老师调整到课程Y,调整之后公布课程X 成绩的时间推迟 一天,公布课程Y 成绩的时间提前一天;每次操作产生A 不愉快度。
  2. 增加一部分老师负责学科Z,这将导致学科Z 的出成绩时间提前一天;每次操 作产生B 不愉快度。 上面两种操作中的参数X, Y, Z 均可任意指定,每种操作均可以执行多次,每次执 行时都可以重新指定参数。 现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快 度之和即可。 【输入格式】 从文件exam.in 中读入数据。 第一行三个非负整数A, B,C ,描述三种不愉快度,详见【问题描述】; 第二行两个正整数n, m(1 ≤n, m ≤105) ,分别表示学生的数量和课程的数量; 第三行n 个正整数ti ,表示每个学生希望的公布成绩的时间; 第四行m 个正整数bi ,表示按照原本的计划,每门课程公布成绩的时间。 【输出格式】 输出到文件exam.out 中。 输出一行一个整数,表示最小的不愉快度之和。 【样例1 输入】 100 100 2 4 5 5 1 2 3 1 1 2 3 3 第2 页 共9 页

2017 年全国青少年信息学奥林匹克竞赛上海市代表队选拔 第一试期末考试(exam) 【样例1 输出】 6 【样例1 说明】 由于调整操作产生的不愉快度太大,所以在本例中最好的方案是不进行调整; 全部 5 的门课程中,最慢的在第3 天出成绩; 同学1 希望在第5 天或之前出成绩,所以不会产生不愉快度; 同学2 希望在第1 天或之前出成绩,产生的不愉快度为(3 −1) ∗2 = 4; 同学3 希望在第2 天或之前出成绩,产生的不愉快度为(3 −2) ∗2 = 2; 同学4 希望在第3 天或之前出成绩,所以不会产生不愉快度; 不愉快度之和为4 + 2 = 6 。 【样例2 输入】 3 5 4 5 6 1 1 4 7 8 2 3 3 1 8 2 【样例2 输出】 33 【样例3】 见选手目录下的exam/exam3.in 与exam/exam3.ans。 【数据范围和约定】 测试点 n, m, ti, bi A,B,C 1,2 1 ≤n, m, ti, bi ≤2, 000 A = 109; B = 109; 0 ≤C ≤102 3,4 0 ≤A,C ≤102; B = 109 5,6,7,8 0 ≤B ≤A ≤102; 0 ≤C ≤102 9,10,11,12 0 ≤A, B,C ≤102 13,14 1 ≤n, m, ti, bi ≤105 0 ≤A, B ≤105;C = 1016 15,16,17,18,19,20 0 ≤A, B,C ≤105 第3 页 共9 页