来自FallDream 的博客，未经允许，请勿转载，谢谢。

---

有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度。对于第i门课程，按照原本的计划，会在第bi天公布成绩。有如下两种操作可以调整公布成绩的时间：1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可

n,m<=100000

 

很容易发现不愉快度是一个下凹的函数 所以可以三分= =

第一次写三分 莫名1A了

#include
      
       #include
       
        #include
        
         #define MN 100000#define ll long longusing namespace std;inline int read(){    ll x = 0; char ch = getchar();    while(ch < '0' || ch > '9') ch = getchar();    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x;}int n,m,t[MN+5],s[MN+5];ll A,B,C,ans=1e18;ll calc(int tms){    ll sum=0,left=0,need=0;    for(int i=1;i<=n;++i) sum+=C*max(0,tms-t[i]);    for(int i=1;i<=m;++i)        if(s[i]>tms) need+=s[i]-tms;        else left+=tms-s[i];    if(B
         
          =need) return sum+need*A;    else return sum+left*A+(need-left)*B;}void Solve(int l,int r){    if(r-l<=1)    {        for(int i=l;i<=r;++i) ans=min(ans,calc(i));        return;    }    int m1=(r-l+1)/3+l,m2=(r-l+1)/3*2+l;    if(calc(m1)