期末考试

Time Limit: 20 Sec Memory Limit: 512 MB

Description

有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所有课程的成绩。

如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度

对于第i门课程，按照原本的计划，会在第bi天公布成绩

有如下两种操作可以调整公布成绩的时间

1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。

2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。

上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。

现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可

Input

第一行三个非负整数A,B,C，描述三种不愉快度，详见【问题描述】；

第二行两个正整数n,m(1≤n,m≤105)，分别表示学生的数量和课程的数量；

第三行n个正整数ti，表示每个学生希望的公布成绩的时间；

第四行m个正整数bi，表示按照原本的计划，每门课程公布成绩的时间。

Output

输出一行一个整数，表示最小的不愉快度之和。

Sample Input

100 100 2
　4 5
　5 1 2 3
　1 1 2 3 3

Sample Output

HINT

Solution

首先，由于学生需要知道所有的成绩，这意味着即使只有一个成绩不知道，代价也是要算的，那么显然答案只和所有成绩都发出的时间有关。
　　显然，如果我们知道了所有成绩都发出的时间，必然是可以算出最小的不愉快度的，对于一个最后日期x，我们运用贪心得到不愉快度：
　　　　1.由于A策略有负面影响，B策略没有，所有在A<B的情况下才有可能用A
　　　　2.如果我们需要用A，显然能用的次数是：所有天数在x前面的 (x-天数)，剩下的用B补满。
　　然后，我们大胆猜测可以三分！这样我们就能AC啦。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000001;
const s64 INF = 1e18;

int A,B,C,n,m;
int t[ONE],b[ONE],MaxN;
s64 Ans = INF;
int Now;

inline s64 get()
{
    s64 res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

s64 Judge(s64 x)
{
    s64 res = 0, num1 = 0, num2 = 0;
    for(int i=1;i<=n;i++) res += max(x-t[i],0LL) * C;
    for(int i=1;i<=m;i++) num1 += max(x-b[i],0LL), num2 += max(b[i]-x,0LL);
    if(A > B) res += num2 * B;
    else
    {
        res += min(num1,num2) * A;
        res += max((num2-num1) * B,0LL);
    }

    Ans = min(Ans,res);
    return res;
}

int main()
{
    A=get();    B=get();    C=get();
    n=get();    m=get();
    for(int i=1;i<=n;i++) t[i]=get(), MaxN=max(MaxN,t[i]);
    for(int i=1;i<=m;i++) b[i]=get();

    if(C >= 1e16)
    {
        for(int i=1;i<=n;i++) MaxN=min(MaxN,t[i]);
        printf("%lld",Judge(MaxN));
    }

    s64 a,b,pass;
    s64 l = 0, r = MaxN+1;
    while(l < r-2)
    {
        pass = (r-l)/3;
        a = l+pass; b = r-pass;
        if(Judge(a) < Judge(b)) r = b;
        else l = a;
    }

    printf("%lld",Ans);

}